Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 30ae323

Browse files
committed
Do some code formatting on QuickSort algorithm.
1 parent bf5d7b3 commit 30ae323

File tree

3 files changed

+42
-21
lines changed

3 files changed

+42
-21
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@ a set of rules that precisely defines a sequence of operations.
7878
* [Insertion Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort)
7979
* [Heap Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort)
8080
* [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
8282
* [Shellsort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort)
8383
* **Tree**
8484
* [Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS)

‎src/algorithms/sorting/quick-sort/QuickSort.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
import Sort from '../Sort';
22

33
export default class QuickSort extends Sort {
4+
/**
5+
* @param {*[]} originalArray
6+
* @return {*[]}
7+
*/
48
sort(originalArray) {
59
// Clone original array to prevent it from modification.
610
const array = [...originalArray];
Lines changed: 37 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,51 @@
11
import Sort from '../Sort';
22

33
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.
55
*
66
* 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 {*[]}
813
*/
9-
sort(originalArray, inputLow,inputHigh) {
14+
sort(originalArray, inputLowIndex,inputHighIndex) {
1015
// 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;
1834
};
1935

20-
const pivot = array[h];
36+
const pivot = array[highIndex];
2137
this.callbacks.visitingCallback(array[pivot]);
22-
let firstRunner = l - 1;
2338

24-
for (let secondRunner = l; secondRunner < h; secondRunner += 1) {
39+
let firstRunner = lowIndex - 1;
40+
for (let secondRunner = lowIndex; secondRunner < highIndex; secondRunner += 1) {
2541
if (this.comparator.lessThan(array[secondRunner], pivot)) {
2642
firstRunner += 1;
2743
swap(firstRunner, secondRunner);
2844
}
2945
}
3046

3147
if (this.comparator.lessThan(pivot, array[firstRunner + 1])) {
32-
swap(firstRunner + 1, h);
48+
swap(firstRunner + 1, highIndex);
3349
}
3450

3551
return firstRunner + 1;
@@ -40,20 +56,21 @@ export default class QuickSortInPlace extends Sort {
4056
* still have to set `high`'s default within the function as we
4157
* don't have access to `array.length - 1` when declaring paramaters
4258
*/
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;
4561

4662
// 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);
4965
/*
5066
* `partition()` swaps elements of the array based on their comparison to the `hi` parameter,
5167
* and then returns the index where swapping is no longer necessary, which can be best thought
5268
* of as the pivot used to split an array in a non-in-place quicksort
5369
*/
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);
5672
}
73+
5774
return array;
5875
}
5976
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /