How does QuickSort Work

Step 1) First, find the “pivot” element in the array.

Step 2) Start the left pointer at the first element of the array.

Step 3) Start the right pointer at the last element of the array.

Step 4) Compare the element pointing with the left pointer, and if it is less than the pivot element, then move the left pointer to the right (add 1 to the left index). Continue this until the left side element is greater than or equal to the pivot element.

Step 5) Compare the element pointing with the right pointer. If it is greater than the pivot element, move the right pointer to the left (subtract 1 to the right index). Continue this until the right-side element is less than or equal to the pivot element.

Step 6) Check if the left pointer is less than or equal to a right pointer, then saw the elements in these pointers’ locations.

Step 7) Increment the left pointer and decrement the right pointer.

Step 8) If the left pointer index is still less than the right pointer’s index, repeat the process; else, return the left pointer’s index.

So, let us see these steps with an example. Let us consider an array of elements which we need to sort is [5,3,7,6,2,9].

Here are the steps to perform Quick sort that is being shown with an example [5,3,7,6,2,9].

STEP 1) Determine pivot as a middle element. So, 7 is the pivot element.

STEP 2) Start left and right pointers as first and last elements of the array, respectively. The left pointer points to 5 at index 0, and the right pointer points to 9 at index 5.

STEP 3) Compare the left pointer element with the pivot element, since 5 < 6 shift left pointer to the right to index 1.

STEP 4) Now, still 3 <6, so shift the left pointer to one more index to the right. Now 7 > 6 stops incrementing the left pointer, and now the left pointer is index 2.

STEP 5) Now, compare the value at the right pointer with the pivot element. Since 9 > 6, move the right pointer to the left. Now, as 2 < 6, stop moving the right pointer.

STEP 6) Swap both values present at left and right pointers with each other.

STEP 7) Move both pointers one more step.

STEP 8) Since 6 = 6, move pointers to one more step and stop as the left pointer crosses the right pointer and returns the left pointer’s index.

Here, based on the above approach, we need to write code for swapping elements and partitioning the array as mentioned in the above steps.

Example:

var items = [5,3,7,6,2,9];
function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function: partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]