Quick Sort

Time Complexity

Space Complexity

Overview

After learning comparison-based algorithms, now we get into the 'heavy lifters' - divide-and-conquer algorithms. Divide and conquer is a separate paradigm/type of algorithm design and the main idea is to break down the problem(input) into smaller, easier to work with problems. Solve them individually and then use them to form the output. These types of algorithms can be more difficult to understand and implement but can be more efficient and quick.

That being said, let's proceed with the star of this section - the famous QuickSort!

Quicksort is an efficient sorting algorithm that employs a divide-and-conquer strategy. It begins by selecting a pivot element (could be first, last or middle element) from the array and then divides the remaining elements into two groups: those smaller than the pivot and those greater than it. This process is applied recursively to these subgroups until the entire array is sorted.

So let's explain the sorting from the animation, step by step

We have the initial input of [5, 3, 7, 6, 1, 2, 4]

1. Select the pivot. Usually selecting the mid element as pivot is good for more randomness and ease of use but in this case, we choose the pivot to be the last element, which is 4.

2. Now we need to partition the array by rearranging the elements such that all elements less than the pivot (4) are to its left, and all elements greater than the pivot are to its right.

   After the partitioning we have: [3, 1, 2] [4] [5, 7, 6]

   The pivot (4) is in its final sorted position - we are sure that all elements to the left are smaller than 4 and all to the right are larger!

3. Now Recursively sort sub-arrays - the algorithm applies the same process to the sub-arrays on the left and right of the pivot.

   • Left sub-array: [3, 1, 2]

     • Pivot: 2
     • After partitioning: [1] [2] [3]

   • Right sub-array: [5, 7, 6]

     • Pivot: 6
     • After partitioning: [5] [6] [7]

   The sub-arrays are already sorted (containing only one element), so no further partitioning or sorting is needed for these cases.

4. As final step, we just need to combine the sorted sub-arrays and consider the whole array as sorted [1, 2, 3, 4, 5, 6, 7].

Now that we know how QuickSort works, let's get back to theory again!

We mentioned that QuickSort is an efficient algorithms, it's also a... quick algo (pun intended). The time complexity of the Quicksort algorithm is generally O(n log n) on average, with "n" being the number of elements in the input array. This makes Quicksort one of the most efficient sorting algorithms available, especially for large datasets.

But as with everything in life, there's a catch! This is the average performance of the algorithm which is fantastic and on average makes it the fastest algorithm. But if we are not lucky, we may get into the scenario of the worst performance which is O(n^2) and... that's not so great.

But why do we even mention the average performance if time complexity is generally mentioned to indicate the worst possible scenario? Because QuickSort can be optimized relatively easily to avoid the worst scenario and when it's used properly, we assume that we will be in the average time complexity. Example of an optimisation could be choosing a random pivot - this will ensure, well, randomness. And on big enough datasets, randomness leads to, well... average performance! And to further optimize it, we can even make a 'hybrid' QuickSort that uses another algorithm for sub-arrays that are too small to have enough randomness in pivot choosing.

So QuickSort is a good algorithms as long as we use it properly. And it shines even more if we compare it to an algorithm like Selection Sort where the Big O time complexity is always O(n^2), even in the best scenario.

Code

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
 
# Example usage:
input_list = [5, 3, 7, 6, 1, 2, 4]
sorted_list = quick_sort(input_list)
print(sorted_list)
 
 

function quick_sort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
    
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return [...quick_sort(left), pivot, ...quick_sort(right)];
}
 
// Example usage:
const inputArray = [5, 3, 7, 6, 1, 2, 4];
const sortedArray = quick_sort(inputArray);
console.log(sortedArray);
 
 

import java.util.Arrays;
 
public class QuickSort {
 
    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 6, 1, 2, 4};
        sortArray(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
 
    public static void sortArray(int[] array) {
        performSort(array, 0, array.length - 1);
    }
 
    private static void performSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partitionArray(array, low, high);
            performSort(array, low, pivotIndex - 1);
            performSort(array, pivotIndex + 1, high);
        }
    }
 
    private static int partitionArray(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
 
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swapElements(array, i, j);
            }
        }
 
        swapElements(array, i + 1, high);
        return i + 1;
    }
 
    private static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
 
 

#include <stdio.h>
 
void swap_elements(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int partition_array(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
 
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap_elements(&arr[i], &arr[j]);
        }
    }
    swap_elements(&arr[i + 1], &arr[high]);
    return i + 1;
}
 
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition_array(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}
 
// Example usage:
int main() {
    int elements[] = {5, 3, 7, 6, 1, 2, 4};
    int num_elements = sizeof(elements) / sizeof(elements[0]);
    quick_sort(elements, 0, num_elements - 1);
 
    printf("Sorted array: ");
    for (int i = 0; i < num_elements; i++) {
        printf("%d ", elements[i]);
    }
    printf("\n");
 
    return 0;
}
 
 

function quick_sort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[count($arr) - 1];
    $left = $right = array();
 
    foreach ($arr as $value) {
        if ($value < $pivot) {
            $left[] = $value;
        } elseif ($value > $pivot) {
            $right[] = $value;
        }
    }
 
    return array_merge(quick_sort($left), array($pivot), quick_sort($right));
}
 
// Example usage:
$input_array = array(5, 3, 7, 6, 1, 2, 4);
$sorted_array = quick_sort($input_array);
print_r($sorted_array);