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:
- 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.
- 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.
- Recursively splits the left and right subarrays using the 1st and the 2nd step until each subarray has one element left.
- 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))
}
-
First, an array of unsorted elements are created.
//nums is the given array const nums = [6,5,2,9,1,3,11,4];
-
Then the function
qSort
, to perform the quicksort algorithm. With thearr
parameter to receive the array.
//QuickSort Function function qSort(arr){ }
-
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
-
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
andright
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
andright
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.
-
At this point, all elements in the array are finally sorted. The last step returns all sorted elements to the
newArray
by concatenating theleft
, thepivot
, and theright
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.
-
Best Case [O(nlog n)]: The algorithm runs faster than other cases when the pivot is always selected at the middle element.
-
Worst Case [O(n2)]: This happens when the pivot selected is the largest or smallest element leaving one of the sub-arrays always empty.
Average Case [O(n*log n)]: This case happens when none of the above occur.
To get more information about quicksort algorithm you can check the following links below:
Latest comments (0)