Segun Olumide

Posted on

# QuickSort Algorithm Simplified

QuickSort is a sorting algorithm that uses a divide and conquer strategy to sort out elements in an array. This strategy uses the following steps:

1. Selects a pivot element from the array, which can be picked in various ways.
• Pivot set from the first element.
• Pivot set from the last element.
• Set a random element as a pivot.
• Use median as the pivot.
2. Uses the pivot to divide the array into subarrays. This process is called partitioning. The pivots partitions elements less than itself to the left side, and elements that are greater are to the right of the pivot.
3. Recursively splits the left and right subarrays using the 1st and the 2nd step until each subarray has one element left.
4. Once the process is complete, the element already gets sorted. Finally, combines the sorted elements back to an array.

## QuickSort Partitioning Algorithm with Javascript

Here is an example of a quicksort function in javascript with a breakdown process of each statement.

``````const nums = [6,5,2,9,1,3,11,4];
function qSort(arr){

if(arr.length <= 1){
return arr
}
let pivot = arr.pop(), left = [], right = [], newArray =[],  length = arr.length
for(let index = 0; index < length; index++){
if(arr[index] <= pivot){
left.push(arr[index])
}
else{
right.push(arr[index])
}
}
return newArray.concat(qSort(left), pivot, qSort(right))
}
``````
1. First, an array of unsorted elements are created.

``````//nums is the given array
const nums = [6,5,2,9,1,3,11,4];
``````
2. Then the function `qSort`, to perform the quicksort algorithm. With the `arr` parameter to receive the array.

``````//QuickSort Function
function qSort(arr){

}
``````
3. A condition is then set to make sure the array (`arr`) provided is not empty and does not contain only one element. If the array has less than one element, it will return that array but proceeds to the next step if it includes more than one element.

``````function qSort(arr){
// if array contains less than one element, return the array
if(arr.length <= 1){
return arr
}
// if array contains more than one element, proceed to next statement
``````
4. The next step is to choose a pivot. In this case, the pivot is set to pick only the last element in the array with the `left` and `right` array for partitioning. `newArray` will append all elements to a new sorted array.

``````let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
``````

A `left` and `right` array are created to partition the elements for the pivot. The pivot position lesser elements to the left and greater elements to the right.

``````let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
for(let index = 0; index < length; index++){
// push elements less than pivot to the left
if(arr[index] <= pivot){
left.push(arr[index])
}
// push elements higher than pivot to the right
else{
right.push(arr[index])
}
``````

This process continuous and breaks into partitions until one element is left.

5. At this point, all elements in the array are finally sorted. The last step returns all sorted elements to the `newArray` by concatenating the `left`, the `pivot`, and the `right` array.

``````let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
for(let index = 0; index < length; index++){
// push elements less than pivot to the left
if(arr[index] <= pivot){
left.push(arr[index])
}
// push elements higher than pivot to the right
else{
right.push(arr[index])
}
return newArray.concat(qSort(left), pivot, qSort(right))
``````

You can test the code using this link - Run quicksort with javascript.

## How long it takes to run QuickSort Algorithm

There are three different time cases it will take the algorithm to run. The best case, worst case and average case.

1. Best Case [O(nlog n)]: The algorithm runs faster than other cases when the pivot is always selected at the middle element.

2. Worst Case [O(n2)]: This happens when the pivot selected is the largest or smallest element leaving one of the sub-arrays always empty.

3. Average Case [O(n*log n)]: This case happens when none of the above occur.