Quick Sort Algorithm
The quick sort algorithm is a sorting method that depends on having a "pivot" somewhere in the array - could be random, and then integers the come before the pivot are compared/swapped with integers coming after the pivot, until everything to the left of the pivot is smaller, and everything to the right of the pivot is larger. Then, once we have this "division" into two separate sections of the array, we repeat the process with each section, continuing like this until everything is arranged. The main key for this algorithm is making the process recursive. Meaning that each time after you've sorted what you need, you're going to call the function again inside of itself, on the values that you've just sorted - doing this continuously until you have the desired result.
ALGORITHM QuickSort(arr, left, right)
if left < right
// Partition the array by setting the position of the pivot value
DEFINE position <-- Partition(arr, left, right)
// Sort the left
QuickSort(arr, left, position - 1)
// Sort the right
QuickSort(arr, position + 1, right)
ALGORITHM Partition(arr, left, right)
// set a pivot value as a point of reference
DEFINE pivot <-- arr[right]
// create a variable to track the largest index of numbers lower than the defined pivot
DEFINE low <-- left - 1
for i <- left to right do
if arr[i] <= pivot
low++
Swap(arr, i, low)
// place the value of the pivot location in the middle.
// all numbers smaller than the pivot are on the left, larger on the right.
Swap(arr, right, low + 1)
// return the pivot index point
return low + 1
ALGORITHM Swap(arr, i, low)
DEFINE temp;
temp <-- arr[i]
arr[i] <-- arr[low]
arr[low] <-- tempTo start this quick sort, we'll instantiate our function and some variables. "quickSort" will be our function name, "left" will be an empty array that'll hold out left side, also "right" that'll do the same for the right side, "newArray" which will be an empty placeholder array for our newly sorted values, and our "pivot" which for this scenario we'll use the last element in our original array, and finally a "length" variable, which is equal to the length of our original array, just to keep thing simple.
Now we'll start with a for loop, which will begin at 0, go through the length of the array, and increment by 1. We'll then define an "if" statement. If the current index position at our array is less than or equal to our pivot value, we will push it into our previously empty "left" array. Else, we'll push it into our "right" array.
Next we'll concatenate our two arrays - calling our original "quickSort" function with "left" as its input, "pivot" in the middle, and "quickSort" with "right" as its input. Now we can return our new array, and it is fully sorted.
function quickSort(origArray) {
if (origArray.length <= 1) {
return origArray;
} else {
var left = [];
var right = [];
var newArray = [];
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) {
if (origArray[i] <= pivot) {
left.push(origArray[i]);
} else {
right.push(origArray[i]);
}
}
return newArray.concat(quickSort(left), pivot, quickSort(right));
}
}