Quick Sort is a highly efficient sort algorithm, mainly because it partitions the array into smaller chunks. We have to provide/compute a special value called the pivot. Based on the pivot the array is divided into two sections. One section will hold values smaller than the pivot, and the other section or subarray will contain all values greater then the pivot.

Once we have the two smaller arrays we need to recursively call the quicksort twice one call will handle the small values section and another call will handle/process all the greater than pivot values.

helper method to do the swapping:

swap = (array, i, j) =>
{   
    let temp = 0;;
    temp = array[ i ];
    array[ i ] = array[ j ];
    array[ j ] = temp;

    if (array[ i ] != array[ j ])
    createRow(rowCtr, array);
    rowCtr++;
}

In the code below we will always use the last element of the array as PIVOT. This is where we will do the swapping of array elements according to the pivot comparison <= or > array value.

partition = ( array, low, high) => 
{
    let pivot = array[high];   
    let i = (low - 1);         
    for (let j = low; j <= high- 1; j++)
    {
        if (array[j] <= pivot)
        {
            i++;    
            swap(array, i, j);
        }
    }
    swap(array, i+1, high);
    return (i + 1);
}

The main quickSort function, will call the partition function and it will call itself twice.

passing the smaller array part with starting index of 0 and ending index of pivot - 1.
passing the larger array part with starting index of pivot + 1 and ending index or length of array - 1.

It will return the fully sorted array.

quickSort = ( array, startIdx, endIdx) =>    
{
    if(startIdx < endIdx)
    {
        let middle = partition(array, startIdx, endIdx);
        quickSort(array, startIdx, middle-1);
        quickSort(array, middle+1, endIdx);
    }
    return array;
}

Quick Sort Algorithm

Please see live code below:

Thank for reading this article.

Let's Connect

Next article: undecided