Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
'use strict';
function swap(arr, ind1, ind2) {
let temp = arr[ind1];
arr[ind1] = arr[ind2];
arr[ind2] = temp;
}
function quickSortInPlace(arr, left, right) {
left = left || 0;
right = typeof(right) == 'undefined' ? arr.length - 1 : right;
// 1. If left is less than right, declare a letiable called partitionIndex
if(left < right) {
// which is equal to the result of a call to partition, passing in arr, left, and right.
let partitionIndex = partition(arr, left, right);
// After the call to partition, perform a quicksort to the two subarrays
// to the left and right of the partitionIndex.
quickSortInPlace(arr, left, partitionIndex - 1);
quickSortInPlace(arr, partitionIndex + 1, right);
}
return arr;
// 2. Return arr.
}
function partition(arr, left, right) {
// 1. Set the pivot value to be the value at the left index,
let pivotValue = arr[left];
// and set a letiable called partitionIndex equal to left.
let partitionIndex = left;
// The partitionIndex will help us keep track of where to perform our swaps so that we wind up with values correctly placed on either side of the pivot.
// 2. For every index greater than left and less than right + 1,
for (let i = left + 1; i < right + 1; i++) {
// compare the array value to the pivot value.
// 3. If the array value at the given index is less than the pivot value,
if(arr[i] < pivotValue) {
//increment the partition index and swap the array value with the value at the partition index.
partitionIndex++;
swap(arr, i, partitionIndex);
}
}
swap(arr, left, partitionIndex);
// 4. At the end, swap the pivot value with the value at the partition index
//(this ensures that the pivot ends up in between values less than it and values greater than it).
// 5. Return the partition index.
return partitionIndex;
}
function quickSort(arr) {
// 1. If the length of the array is less than 2, it is already sorted, so return it.
if(arr.length < 2) {
return arr;
}
// 2. Otherwise, create two empty arrays (one for the left and one for the right),
// and set the first value in arr equal to the pivot.
let left = [];
let right = [];
let pivotValue = arr[0];
// 3. Compare every element in the array to the pivot.
for (let i = 1; i < arr.length; i++) {
//If the element is less than the pivot,
if(arr[i] < pivotValue) {
// push it into the left array.
left.push(arr[i]);
} else {
// Otherwise, push it into the right array.
right.push(arr[i]);
}
}
// 4. Recrusively call quickSort on the left array and the right array,
left = quickSort(left);
right = quickSort(right);
// then concatenate these arrays together with the pivot value in between them,
left.push(pivotValue);
return left.concat(right);
// and return this larger array.
}
let gifNums = [6,5,3,1,8,7,2];
// console.log(quickSort(gifNums));
// gifNums = [6,5,3,1,8,7,2];
// console.log(partition(gifNums, 0, gifNums.length - 1))
// console.log(gifNums);
console.log(quickSortInPlace(gifNums));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment