Quick Sort Using Javascript

Quick sort is a sorting algorithm to sort list of unsorted element in an array, it is a divide and conquer algorithms(basically dividing the problem into sub problems until it become easy to solve), that works by selecting a pivot element from the array and partitioning the elements into two sub arrays, one with the elements that are less than the pivot and other with the elements that are greater than the pivot.

You can choose a pivot:

• Starting element from the array
• Last element from the array
• Middle element of the array
• Median of the array

For this blog, we’ll use last element approach.

TIME COMPLEXITY: Quick sort has a time complexity of O(n*n), with average complexity of O(nlog(n)).

Sudo code:

/**
* Checking if the array is empty or not, if it is empty then return
* Selecting a pivot element, in our case it is the last element in the array
* Initialise an empty left array variable(to store less values) and right array variable(to store greater values).
* Initializing a loop to the length-1 of the array, so that we can compare element if they are less than or greater than the pivot
* Inside the loop, check if current value is less or greater than pivot, if less than put in left array else in right array.
* So now, we have left array(that has less values), we have pivot that is the middle (as it is greater than less values and less than greater values) and a right array(that has greater values).
* We need to use the recursion to call the function , until we reach empty array and return the output
*/

Let’s jump into code:

const quickSort = (unSortedArray) => {
// checking if array is not empty
if (!unSortedArray.length) return [];
// selecting the pivit from the array
let pivotElement = unSortedArray[unSortedArray.length - 1];
// array to store lesser values
let leftArray = [];
// array to store greater values
let rightArray = [];
//iterating through length-2 elements
for (let i = 0; i < unSortedArray.length - 1; i++) {
if (unSortedArray[i] < pivotElement) {
leftArray.push(unSortedArray[i]);
} else {
rightArray.push(unSortedArray[i]);
}
}
return [...quickSort(leftArray), pivotElement, ...quickSort(rightArray)];
};
console.log(quickSort([-6, 20, 8, 4, -2]));

Quick sort is very simple if you understand it and practice it. Working with algorithms gives you a mindset of solving a problem with much better approach and already proven methods and choice of data structure.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we are covering few of the most commonly used algorithms.

In the next blog, we’ll go through Merge sort.