DEV Community

Cover image for The easiest way to understanding Quick Sort🔥
Igiraneza Honorine
Igiraneza Honorine

Posted on • Updated on

The easiest way to understanding Quick Sort🔥

Quick sort has been an algorithm I was afraid of learning😢, pretending that it is too hard and require too much time to understand it, but now here I am explaining to you how straight forward it is using a short article written for it. Simple recursive function is required to fully understand quick sort.

The first thing to know is that we use pivot point while comparing to other items in order to get the left side and right side of pivot and repeat the process. With that information we can get started.

Here I use pivotIndex variable to compare item on that index with other items, swapIndex variable to track index which will be swapped with small item found on the left side of pivot, and variable i to loop through all items and know which current item we are comparing to the pivot.

swapIndex is initially set at the same index of pivotIndex. Whenever item smaller than pivot item is found, we increment 1 to swapIndex and swap item on swap index with current item we are on while looping with i. After that we swap pivot item with item on swap index.

Swap function

function swapFn(array, firstIndex, secondIndex) {
    let temp = array[firstIndex]
    array[firstIndex] = array[secondIndex]
    array[secondIndex] = temp
}
Enter fullscreen mode Exit fullscreen mode

Below is the algorithm that we use recursively to sort elements with Quick sort.
Quick Sort algorithm
Step 1: Start
Step 2: Declare variables pivotIndex, swapIndex and i.
Step 3: Initialize variables pivotIndex←0 swapIndex← pivotIndex, i= pivotIndex +1

Step 4: Repeat the steps until i≤array.length-1
if array[i] is less than array[pivotIndex] then
swapIndex++
swapFn(array[swap], array[i])
swapFn(array[swapIndex], array[pivotIndex])
Step 5: OUTPUT swapIndex
Step 6: Stop

Swap Index where pivot will be swapped function

function pivotFn(array, pivotIndex=0, endIndex=array.length-1) { 
    let swapIndex = pivotIndex
    for (let i = pivotIndex + 1; i <= endIndex; i++) {
        if (array[i] < array[pivotIndex]) {
            swapIndex++
            swapFn(array, swapIndex, i)
        }
    }
    swapFn(array, pivotIndex, swapIndex)
    return swapIndex
}
Enter fullscreen mode Exit fullscreen mode

Follow along this diagram to see how it works.

Image description

Image description

function quickSort(array, left=0, right=array.length-1) {
if(left < right) {
let pivotIndex = pivot(array, left, right)
quickSort(array, left, pivotIndex-1)
quickSort(array, pivotIndex+1, right)
}
return array
}

Test Quick sort by calling this function: quickSort([4,6,1,7,3,2,5])

To sum up, We’ve got the left side with red color and the right side with green color. We do the same above process to both sides by comparing items with the pivot and swap if item is less than the pivot and then swap the pivot with the swap index.

Top comments (0)