@@ -11,12 +11,21 @@ export default class QuickSortInPlace extends Sort {
1111 *@param {number } inputHighIndex
1212 *@return {*[] }
1313 */
14- sort ( originalArray , inputLowIndex , inputHighIndex ) {
15- // Destructures array on initial passthrough, and then sorts in place.
16- const array = inputLowIndex === undefined ?[ ...originalArray ] :originalArray ;
14+ sort (
15+ originalArray ,
16+ inputLowIndex = 0 ,
17+ inputHighIndex = originalArray . length - 1 ,
18+ recursiveCall = false ,
19+ ) {
20+ // Copies array on initial call, and then sorts in place.
21+ const array = recursiveCall ?originalArray :[ ...originalArray ] ;
1722
1823/**
19- * Partition array segment and return index of last swap
24+ * `partition` operates on the subarray between lowIndex and highIndex, inclusive.
25+ * it arbitrarily chooses the last element in the subarray as the pivot.
26+ * then, it partially sorts the subarray into elements than are less than the pivot,
27+ * and elements that are greater than or equal to the pivot.
28+ * each time `partition` is executed, the pivot element is in its final sorted position.
2029 *
2130 *@param {number } lowIndex
2231 *@param {number } highIndex
@@ -28,47 +37,38 @@ export default class QuickSortInPlace extends Sort {
2837 *@param {number } rightIndex
2938 */
3039const swap = ( leftIndex , rightIndex ) => {
31- const tempVariable = array [ leftIndex ] ;
40+ const temp = array [ leftIndex ] ;
3241array [ leftIndex ] = array [ rightIndex ] ;
33- array [ rightIndex ] = tempVariable ;
42+ array [ rightIndex ] = temp ;
3443} ;
3544
3645const pivot = array [ highIndex ] ;
46+ // visitingCallback is used for time-complexity analysis
3747this . callbacks . visitingCallback ( array [ pivot ] ) ;
3848
39- let firstRunner = lowIndex - 1 ;
40- for ( let secondRunner = lowIndex ; secondRunner < highIndex ; secondRunner += 1 ) {
41- if ( this . comparator . lessThan ( array [ secondRunner ] , pivot ) ) {
42- firstRunner += 1 ;
43- swap ( firstRunner , secondRunner ) ;
49+ let partitionIndex = lowIndex ;
50+ for ( let currentIndex = lowIndex ; currentIndex < highIndex ; currentIndex += 1 ) {
51+ if ( this . comparator . lessThan ( array [ currentIndex ] , pivot ) ) {
52+ swap ( partitionIndex , currentIndex ) ;
53+ partitionIndex += 1 ;
4454}
4555}
4656
47- if ( this . comparator . lessThan ( pivot , array [ firstRunner + 1 ] ) ) {
48- swap ( firstRunner + 1 , highIndex ) ;
49- }
57+ // The element at the partitionIndex is guaranteed to be greater than or equal to pivot.
58+ // All elements to the left of partitionIndex are guaranteed to be less than pivot.
59+ // Swapping the pivot with the partitionIndex therefore places the pivot in its
60+ // final sorted position.
61+ swap ( partitionIndex , highIndex ) ;
5062
51- return firstRunner + 1 ;
63+ return partitionIndex ;
5264} ;
5365
54- /*
55- * While we can use a default parameter to set `low` to 0, we would
56- * still have to set `high`'s default within the function as we
57- * don't have access to `array.length - 1` when declaring parameters
58- */
59- const lowIndex = inputLowIndex === undefined ?0 :inputLowIndex ;
60- const highIndex = inputHighIndex === undefined ?array . length - 1 :inputHighIndex ;
61-
6266// Base case is when low and high converge
63- if ( lowIndex < highIndex ) {
64- const partitionIndex = partition ( lowIndex , highIndex ) ;
65- /*
66- * `partition()` swaps elements of the array based on their comparison to the `hi` parameter,
67- * and then returns the index where swapping is no longer necessary, which can be best thought
68- * of as the pivot used to split an array in a non-in-place quicksort
69- */
70- this . sort ( array , lowIndex , partitionIndex - 1 ) ;
71- this . sort ( array , partitionIndex + 1 , highIndex ) ;
67+ if ( inputLowIndex < inputHighIndex ) {
68+ const partitionIndex = partition ( inputLowIndex , inputHighIndex ) ;
69+ const RECURSIVE_CALL = true ;
70+ this . sort ( array , inputLowIndex , partitionIndex - 1 , RECURSIVE_CALL ) ;
71+ this . sort ( array , partitionIndex + 1 , inputHighIndex , RECURSIVE_CALL ) ;
7272}
7373
7474return array ;