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.

To get more information about quicksort algorithm you can check the following links below:

• Quicksort algorithm by programiz
• Quicksort algorithm by geeksforgeeks
• Quicksort from wikipedia