Quick Sort

Quick Sort swiftly organizes elements by picking a reference point (pivot) and rearranging items so that smaller values gather on one side and larger ones on the other. It repeats this process recursively until everything is in order. This method is super fast, especially for big lists. However, if not managed well, it can slow down in certain situations. Overall, Quick Sort is a speedy and popular way to sort things.

Advantages

1. Exceptionally fast, especially on large datasets.
2. It requires minimal additional memory space due to its in-place sorting nature.
3. Performs well on various data types and is widely used in practice.

Disadvantages

1. Can degrade to O(n^2) if poorly implemented or with specific data patterns.
2. Doesn't always preserve the original order of equal elements in the sorted output.

Visualisation

• array = [3, 5, 1, 2, 4]

i	j				pivot
	3	5	1	2	4

• IF j < pivot THEN i+1 swap(i, j)

	i,j				pivot
	3	5	1	2	4

• Because j and i are in the same place, then nothing changes.

• Keep adding the j until j < pivot

	i	j			pivot
	3	5	1	2	4

	i		j		pivot
	3	5	1	2	4

• Remember, if j < pivot, then i+1 and swap(i, j)

		i	j		pivot
	3	5 (unswap)	1 (unswap)	2	4

		i	j		pivot
	3	1 (swapped)	5 (swapped)	2	4

• Keep adding the j until j < pivot

		i		j	pivot
	3	1	5	2	4

• if j < pivot

		i		j	pivot
	3	1	5	2	4

• then i+1 and swapp(i, j)

			i	j	pivot
	3	1	5 (unswap)	2 unswap	4

			i	j	pivot
	3	1	2 (swapped)	5 (swapped)	4

• IF j = pivot-1 THEN i+1 and swap (i, pivot)

				i,j	pivot
	3	1	2	5 (unswap)	4 (unswap)

				i,j, pivot
	3	1	2	4 (swapped)	5 (swapped)
Left posisition of Pivot					Right posisition of Pivot

Now that’s the end of the first iteration. Next we’ll try to see the position of the pivot. And we’ll do the same thing both for the array in the left position of pivot (4) and the right position.

• Left posisition

i	j		pivot
	3	1	2

• IF j < pivot, add i and swap(i, j) ELSE j++

i		j	pivot
	3	1	2

	i	j	pivot
	3 (unswap)	1 (unswap)	2

	i	j	pivot
	1 (swapped)	3 (uswapped)	2

• IF j = pivot-1 THEN i+1 and swap (i, pivot)

		i, j	pivot
	1	3 (unswap)	2 (unswap)

		i, j, pivot
	1	2 (swapped)	3 (swapped)
Left posisition of Pivot			Right posisition of Pivot

Because the left and right side of pivot is only one number, so the iteration can be stopped.
THE END (for left position)

• For the Right posisition, because there’s only one number, which is 5, so we don’t need to do the iteration.

So here’s the final result of quick sort.

from the second iteration			from the first iteration
1 Left position	2 Left position	3 Left position	4 Initial pivot	5 Right position

Quick sort might be harder to understand, but it’s the fastest algorithm.

You might wonder, how do we pick the pivot?

How do we choose the pivot?

There are many ways to pick the pivot:

1. Pick the first element.
2. Pick the last element.
3. Pick a random element.
4. Pick the median.

• Most implementations will use the first or last element as the pivot, but again it depends on the situation of the array. If the array is nearly sorted, it’s better to pick random/median element, not the first or last.
• In an ideal quicksort algorithm, the pivot should be the middle-most element. So the partition will be in equal size for more effective process

Pseudocode

Pseudocode Algorithm for Quick Sort

quickSort(arr, low, high)
    IF low < high THEN
        // Partition the array and get the pivot index
        pivotIndex = partition(arr, low, high)
        
        // Recursively sort elements before and after the pivot
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)

Pseudocode Algorithm for Partition

function partition(arr, low, high)
    pivot = arr[high] // Choose the pivot (form the last element)
    smaller = low - 1  // Index of smaller element (in the previous example it’s “i”)

    FOR i FROM low TO high - 1 DO
        arr[i] <= pivot THEN // If current element is smaller than or equal to pivot
        smaller = smaller + 1 // Increment index of smaller element
        swap(arr, smaller, i) // Swap arr[smaller] and arr[i]

    swap(arr, smaller + 1, high) // Swap arr[smaller + 1] and arr[high] (pivot)
    return smaller + 1 // Return the partitioning index

Pseudocode Algorithm for Swapping

swap(arr, i, j)
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

Quick Sort Example

C

// Swap function
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int smaller = low - 1;

    for (int i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            smaller++;
            swap(&arr[smaller], &arr[i]);
        }
    }
    swap(&arr[smaller + 1], &arr[high]);
    return (smaller + 1);
}

// Quick Sort Function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {12, 7, 3, 9, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

C++

// Swap function
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int smaller = low - 1;

    for (int i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            smaller++;
            swap(arr[smaller], arr[i]);
        }
    }
    swap(arr[smaller + 1], arr[high]);
    return (smaller + 1);
}

// Quick sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {12, 7, 3, 9, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Java

// Swap function
static void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

// Partition function
static int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int smaller = low - 1;

    for (int i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            smaller++;
            swap(arr, smaller, i);
        }
    }
    swap(arr, smaller + 1, high);
    return (smaller + 1);
}

// Quick sort function
static void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

public static void main(String args[]) {
    int arr[] = {12, 7, 3, 9, 2, 5};
    int n = arr.length;

    quickSort(arr, 0, n - 1);
    System.out.print("Sorted array: ");
    for (int i = 0; i < n; ++i) {
        System.out.print(arr[i] + " ");
    }
}

Python

# Swap function
def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]

# Partition function
def partition(arr, low, high):
    pivot = arr[high]
    smaller = low - 1

    for i in range(low, high):
        if arr[i] <= pivot:
            smaller += 1
            swap(arr, smaller, i)

    swap(arr, smaller + 1, high)
    return smaller + 1

# Quick sort function
def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

arr = [12, 7, 3, 9, 2, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("Sorted array:", end=" ")
for i in range(n):
    print(arr[i], end=" ")

Exercise

What to do?

1. Given an array representing the ages of individuals: [35, 20, 42, 18, 28, 30]. Implement Quick Sort to arrange the ages in ascending order.
2. Consider an array with exam scores: [85, 92, 78, 96, 88, 90]. Use Quick Sort to sort the scores in ascending order.
3. You have an array representing the prices of various products: [12.99, 9.99, 5.49, 15.79, 8.29, 11.59]. Apply Quick Sort to arrange the prices in ascending order.

Want more challenge?

4. Given an array representing elevations in meters: [250, 120, 400, 180, 320, 280]. Write a program using Quick Sort to arrange the elevations in descending order.