| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -78,7 +78,7 @@ a set of rules that precisely defines a sequence of operations. | |||
| 78 | 78 | * [Insertion Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort) | |
| 79 | 79 | * [Heap Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort) | |
| 80 | 80 | * [Merge Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort) | |
| 81 | - * [Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) | ||
| 81 | + * [Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) - in-place and non-in-place implementations | ||
| 82 | 82 | * [Shellsort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort) | |
| 83 | 83 | * **Tree** | |
| 84 | 84 | * [Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS) | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1,6 +1,10 @@ | |||
| 1 | 1 | import Sort from '../Sort'; | |
| 2 | 2 | ||
| 3 | 3 | export default class QuickSort extends Sort { | |
| 4 | + /** | ||
| 5 | + * @param {*[]} originalArray | ||
| 6 | + * @return {*[]} | ||
| 7 | + */ | ||
| 4 | 8 | sort(originalArray) { | |
| 5 | 9 | // Clone original array to prevent it from modification. | |
| 6 | 10 | const array = [...originalArray]; | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1,35 +1,51 @@ | |||
| 1 | 1 | import Sort from '../Sort'; | |
| 2 | 2 | ||
| 3 | 3 | export default class QuickSortInPlace extends Sort { | |
| 4 | - /* Sorting in place avoids unnecessary use of additional memory, but modifies input array. | ||
| 4 | + /** Sorting in place avoids unnecessary use of additional memory, but modifies input array. | ||
| 5 | 5 | * | |
| 6 | 6 | * This process is difficult to describe, but much clearer with a visualization: | |
| 7 | - * http://www.algomation.com/algorithm/quick-sort-visualization | ||
| 7 | + * @see: http://www.algomation.com/algorithm/quick-sort-visualization | ||
| 8 | + * | ||
| 9 | + * @param {*[]} originalArray | ||
| 10 | + * @param {number} inputLowIndex | ||
| 11 | + * @param {number} inputHighIndex | ||
| 12 | + * @return {*[]} | ||
| 8 | 13 | */ | |
| 9 | - sort(originalArray, inputLow, inputHigh) { | ||
| 14 | + sort(originalArray, inputLowIndex, inputHighIndex) { | ||
| 10 | 15 | // Destructures array on initial passthrough, and then sorts in place. | |
| 11 | - const array = inputLow === undefined ? [...originalArray] : originalArray; | ||
| 12 | - // Partition array segment and return index of last swap | ||
| 13 | - const partition = (l, h) => { | ||
| 14 | - const swap = (left, right) => { | ||
| 15 | - const tempVariable = array[left]; | ||
| 16 | - array[left] = array[right]; | ||
| 17 | - array[right] = tempVariable; | ||
| 16 | + const array = inputLowIndex === undefined ? [...originalArray] : originalArray; | ||
| 17 | + | ||
| 18 | + /** | ||
| 19 | + * Partition array segment and return index of last swap | ||
| 20 | + * | ||
| 21 | + * @param {number} lowIndex | ||
| 22 | + * @param {number} highIndex | ||
| 23 | + * @return {number} | ||
| 24 | + */ | ||
| 25 | + const partition = (lowIndex, highIndex) => { | ||
| 26 | + /** | ||
| 27 | + * @param {number} leftIndex | ||
| 28 | + * @param {number} rightIndex | ||
| 29 | + */ | ||
| 30 | + const swap = (leftIndex, rightIndex) => { | ||
| 31 | + const tempVariable = array[leftIndex]; | ||
| 32 | + array[leftIndex] = array[rightIndex]; | ||
| 33 | + array[rightIndex] = tempVariable; | ||
| 18 | 34 | }; | |
| 19 | 35 | ||
| 20 | - const pivot = array[h]; | ||
| 36 | + const pivot = array[highIndex]; | ||
| 21 | 37 | this.callbacks.visitingCallback(array[pivot]); | |
| 22 | - let firstRunner = l - 1; | ||
| 23 | 38 | ||
| 24 | - for (let secondRunner = l; secondRunner < h; secondRunner += 1) { | ||
| 39 | + let firstRunner = lowIndex - 1; | ||
| 40 | + for (let secondRunner = lowIndex; secondRunner < highIndex; secondRunner += 1) { | ||
| 25 | 41 | if (this.comparator.lessThan(array[secondRunner], pivot)) { | |
| 26 | 42 | firstRunner += 1; | |
| 27 | 43 | swap(firstRunner, secondRunner); | |
| 28 | 44 | } | |
| 29 | 45 | } | |
| 30 | 46 | ||
| 31 | 47 | if (this.comparator.lessThan(pivot, array[firstRunner + 1])) { | |
| 32 | - swap(firstRunner + 1, h); | ||
| 48 | + swap(firstRunner + 1, highIndex); | ||
| 33 | 49 | } | |
| 34 | 50 | ||
| 35 | 51 | return firstRunner + 1; | |
@@ -40,20 +56,21 @@ export default class QuickSortInPlace extends Sort { | |||
| 40 | 56 | * still have to set `high`'s default within the function as we | |
| 41 | 57 | * don't have access to `array.length - 1` when declaring paramaters | |
| 42 | 58 | */ | |
| 43 | - const low = inputLow === undefined ? 0 : inputLow; | ||
| 44 | - const high = inputHigh === undefined ? array.length - 1 : inputHigh; | ||
| 59 | + const lowIndex = inputLowIndex === undefined ? 0 : inputLowIndex; | ||
| 60 | + const highIndex = inputHighIndex === undefined ? array.length - 1 : inputHighIndex; | ||
| 45 | 61 | ||
| 46 | 62 | // Base case is when low and high converge | |
| 47 | - if (low < high) { | ||
| 48 | - const partitionIndex = partition(low, high); | ||
| 63 | + if (lowIndex < highIndex) { | ||
| 64 | + const partitionIndex = partition(lowIndex, highIndex); | ||
| 49 | 65 | /* | |
| 50 | 66 | * `partition()` swaps elements of the array based on their comparison to the `hi` parameter, | |
| 51 | 67 | * and then returns the index where swapping is no longer necessary, which can be best thought | |
| 52 | 68 | * of as the pivot used to split an array in a non-in-place quicksort | |
| 53 | 69 | */ | |
| 54 | - this.sort(array, low, partitionIndex - 1); | ||
| 55 | - this.sort(array, partitionIndex + 1, high); | ||
| 70 | + this.sort(array, lowIndex, partitionIndex - 1); | ||
| 71 | + this.sort(array, partitionIndex + 1, highIndex); | ||
| 56 | 72 | } | |
| 73 | + | ||
| 57 | 74 | return array; | |
| 58 | 75 | } | |
| 59 | 76 | } | |
| Back | FazBrowse Home | New Git URL |
0 commit comments