GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — JavaScript/Sorts/QuickSortRecursive.js at master · TheAlgorithms/JavaScript Expand file tree/ Copy pathQuickSortRecursive.jsMore file actions 65 lines (60 loc) · 2.16 KB / Copy pathQuickSortRecursive.jsFile metadata and controls65 lines (60 loc) · 2.16 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 /* Quicksort is the most popular sorting algorithm and there have lots of different implementations but the "recursive" or "Partition in place" is one of the most efficient implementations below we have discussed how to implement it. Partition in place => "in place" Partition in place indicates that we do not need any other space to store the auxiliary array and the term "partition" denotes that we split the list into two parts one is less than the pivot and the other is greater than the pivot and repeats this process recursively and breaks the problem into sub-problems and makes it singular so that the behavior or "divide and conquer" get involved too. Problem & Source of Explanation => https://www.cs.auckland.ac.nz/software/AlgAnim/qsort1a.html */ /** * Partition in place QuickSort. * @param {number[]} inputList list of values. * @param {number} low lower index for partition. * @param {number} high higher index for partition. */ const quickSort = (inputList, low, high) => { if (!Array.isArray(inputList)) { throw new TypeError('Please input a valid list or array.') } if (low < high) { // get the partition index. const pIndex = partition(inputList, low, high) // recursively call the quickSort method again. quickSort(inputList, low, pIndex - 1) quickSort(inputList, pIndex + 1, high) } return inputList } /** * Partition In Place method. * @param {number[]} partitionList list for partitioning. * @param {number} low lower index for partition. * @param {number} high higher index for partition. * @returns {number} `pIndex` pivot index value. */ const partition = (partitionList, low, high) => { const pivot = partitionList[high] let pIndex = low for (let index = low; index <= high - 1; index++) { if (partitionList[index] < pivot) { // swap variables using array destructuring ;[partitionList[index], partitionList[pIndex]] = [ partitionList[pIndex], partitionList[index] ] pIndex += 1 } } ;[partitionList[pIndex], partitionList[high]] = [ partitionList[high], partitionList[pIndex] ] return pIndex } export { quickSort } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |