-Intro to Quick Sort
-Pivot Helper Implementation
-Quick Sort Implementation
Intro to Quick Sort
Quick sort works by selecting one element called the pivot and finding the index where the pivot should end up in the sorted array. Once the pivot is positioned appropriately, quick sort can be applied on either side of the pivot.
Start by picking element 5, then move all the elements that are less than 5 to the left and then all the elements that are greater than 5 to the right.
then recursively repeat this process
Pivot Helper Implementation
All values that are less than the pivot are moved to the left and all values that are greater than pivot are moved to the right. The order on either side does not matter.
function pivot(arr, start=0, end=arr.length+1){
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var pivot = arr[start];
var swapIdx = start;
for(var i = start + 1; i < arr.length; i++){
if(pivot > arr[i]){
swapIdx++;
swap(arr,swapIdx,i);
}
}
swap(arr,start,swapIdx);
return swapIdx;
}
// Version with ES2015 Syntax
function pivot(arr, start = 0, end = arr.length - 1) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// We are assuming the pivot is always the first element
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// Swap the pivot from the start the swapPoint
swap(arr, start, swapIdx);
return swapIdx;
}
pivot([4,8,2,1,5,7,6,3])
Quick Sort Implementation
Calls the pivot helper on the array, when the helper returns to the updated pivot index recursively calls the pivot helper on the subarray to the left of that index and the subarray to the right of that index. Not making any new arrays, this is all happening inside of the existing array.
Quick Sort Example
function pivot(arr, start = 0, end = arr.length - 1) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// We are assuming the pivot is always the first element
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// Swap the pivot from the start the swapPoint
swap(arr, start, swapIdx);
return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length -1){
if(left < right){
let pivotIndex = pivot(arr, left, right) //3
//left
quickSort(arr,left,pivotIndex-1);
//right
quickSort(arr,pivotIndex+1,right);
}
return arr;
}
quickSort([100,-3,2,4,6,9,1,2,5,3,23])
// [4,6,9,1,2,5,3]
// [3,2,1,4,6,9,5]
// 4
// 3,2,1 6,9,5
// 3 6
// 2,1 5 9
// 2
// 1
Top comments (0)