DEV Community

Segun Olumide
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))
}
Enter fullscreen mode Exit fullscreen mode
  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
    

    Selecting last element as pivot

    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.

    Pivot positioning

    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.

    Partition breakdown

  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.

    Best case

  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.

    Worst Case

  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:

Latest comments (0)