Quick Sort Algorithm Using JavaScript

Introduction

Quicksort is a popular sorting algorithm that follows the divide-and-conquer algorithm. The divide-and-conquer algorithm is an approach to solving a large problem by breaking it down into smaller sub-problems recursively. If the sub-problems are small enough, they can now be combined to get the desired output.

How does Quicksort Algorithm work?

Quicksort algorithm works by selecting a pivot which could be any number from an array and then partitioning the array into two sub-arrays where the elements with lesser values come before the pivot and elements with greater values come after the pivot. Then the process is carried out recursively on the sub-arrays of elements with lesser values and separately on sub-arrays of elements with greater values until each sub-arrays contains a single element and the elements can now be combined to form a sorted array.

Pivot selection is an important part of the Quicksort algorithm and there are many techniques that can be used. You can select :

• the first element as the pivot

• the last element as the pivot

• the median number as the pivot

• a random number as the pivot

Visual representation of the Quick Sort Algorithm

Implementing Quicksort Algorithm in JavaScript

function Quicksort(array){
    if(array.length <= 1){
        return array;
    }
    const pivot = array[array.length - 1 ]
    const leftArray = []
    const rightArray = []
    for(let i = 0; i < array.length - 1; i++){
        array[i] < pivot ? leftArray.push(array[i]) : rightArray.push(array[i])
    }
    return[...Quicksort(leftArray), pivot, ...Quicksort(rightArray)]
}
const Arr =[1, 4, 9, 8, 245, 123, 43, 62, 3978, 27, 123, 43, 2, 58, 1, 76, 82]
console.log(Quicksort(Arr))

output:

[ 1,  1,  2,   4,   8, 9,   27, 43,  43,  58, 62, 76, 82, 123, 123, 245, 3978 ]

Let's take a look at how the example is implemented ⬇️

• Declare a function that holds a parameter called array.

• Now you'll declare an If statement to check the length of the array. If the length is less than or equal to one, you'll return the array unaltered.

 if(array.length <= 1){
        return array;
    }

• Next, you'll select a pivot element which is the last element in the array in this case.

const pivot = array[array.length - 1 ]

• Then you will create two empty arrays which are the leftArray and rightArray to compare elements with pivot and place the element accordingly.

const leftArray = []
const rightArray = []

• You will iterate through the array by using a for loop and inside this loop, you will want to check if the element is lesser or greater than the pivot. If the element is lesser than the pivot, you'll push it into the leftArray and if the element is greater than the pivot, you'll push it into the rightArray.

 for(let i = 0; i < array.length - 1; i++){
        array[i] < pivot ? leftArray.push(array[i]) : rightArray.push(array[i])
    }

• Lastly, you will call the Quicksort function recursively on the left and right array to partition the arrays until they get sorted completely.

 return[...Quicksort(leftArray), pivot, ...Quicksort(rightArray)]

References

• Youtube
• Github
• Khanacademy