DEV Community

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
}

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
}

Follow along this diagram to see how it works.

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.