How Quick Sort Algorithm works?

The following steps explain how quicksort works.

First, select an element – as a pivot element.

Compare all elements with the selected pivot element and arrange these in an order such that the elements less than the pivot element are placed on its left side and elements greater than the pivot are placed on its right side. It would be best if you use a swap function to place elements at their place.

Next, perform the same operation on the left and right side elements of the pivot elements in a recursive fashion.

Example of Quick Sort Algorithm using JavaScript

Let’s say you have to sort an array containing integer values.

let arr = [7,3,4,9,1,2];

The following function swaps two numbers in JS.

function swap(arr, left, right) {
    var temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

To perform the partition on the array, use the following function.

function partition(arr, left, right) {

    let middle = arr[Math.floor((right + left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (arr[i] < middle) {
            i++;
        }
        while (arr[j] > middle) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

The next step is to call partition() function recursively to divide and sort the arrays.

function quickSort(arr, left, right) {
    let index;
    if (arr.length > 1) {
        index = partition(arr, left, right);
        if (left < index - 1) {
            quickSort(arr, left, index - 1);
        }
        if (index < right) {
            quickSort(arr, index, right);
        }
    }
    return arr;
}

To call the function, pass the array to quicksort() function as a parameter

let arr = [7, 3, 4, 9, 1, 2];
console.log("Array before sorting :" + arr);
var sorted_arr = quickSort(arr, 0, arr.length - 1);
console.log("Array after sorting :" + sorted_arr);

Output:

CodingPanel Editor

Blog Hero