Practice code with the "Quick Sort" algorithm

The principle of Quick sort algorithm

Quick sort is an efficient sorting algorithm. Here’s how it works:

1. Choose a pivot: select an element from the array (commonly the first, last, or a random element).
2. Partition: rearrange the array so elements less than the pivot come before it, and elements greater come after. The pivot is now in its final position.
3. Recursively sort: apply the same process to the sub-arrays on either side of the pivot.
4. Base case: stop when sub-arrays have one or zero elements, as they are already sorted.

Example

Let’s go through Quick Sort step-by-step with the example array [5, 3, 7, 6, 2, 1, 8].

1. Initial Array: [5, 3, 7, 6, 2, 1, 8]
2. Pivot: 5 (first element)

Step 1: Partitioning

• Elements less than 5: [3, 2, 1]
• Elements equal to 5: [5]
• Elements greater than 5: [7, 6, 8]

The array now looks like: [3, 2, 1] [5] [7, 6, 8]

Step 2: Recursively sort sub-arrays

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

• Pivot: 3
• Partitioning:
  • Elements less than 3: [2, 1]
  • Elements equal to 3: [3]
  • Elements greater than 3: []

The array now looks like: [2, 1] [3] []

Right sub-array [7, 6, 8]:

• Pivot: 7
• Partitioning:
  • Elements less than 7: [6]
  • Elements equal to 7: [7]
  • Elements greater than 7: [8]

The array now looks like: [6] [7] [8]

Step 3: Recursively sort again

Left sub-array [2, 1]:

• Pivot: 2
• Partitioning:
  • Elements less than 2: [1]
  • Elements equal to 2: [2]
  • Elements greater than 2: []

The array now looks like: [1] [2] []

• [6] [7] [8] is already sorted.

Step 4: Combine sorted arrays

• Left part: [1, 2, 3]
• Middle part: [5]
• Right part: [6, 7, 8]

Final sorted array: [1, 2, 3, 5, 6, 7, 8]

The naive simple version

def quicksort(array):
    # Base case: if the array is empty or has one element, it's already sorted
    if len(array) <= 1:
        return array

    # Choose the pivot (last element in this case)
    pivot = array.pop()

    # Lists to hold elements less than and greater than the pivot
    smaller_elements = []
    larger_elements = []

    # Partition the array into smaller_elements and larger_elements lists
    for element in array:
        if element < pivot:
            smaller_elements.append(element)
        else:
            larger_elements.append(element)

    # Recursively sort the smaller_elements and larger_elements lists, and concatenate them with the pivot
    return quicksort(smaller_elements) + [pivot] + quicksort(larger_elements)

# Example usage
arr = [8, 2, 5, 3, 9, 4, 7, 6, 1]
print(quicksort(arr)) # TADA 🎉🥳

This version of quicksort correctly implements the core idea but differs from the “classic” quicksort in a few ways:

• Classic quicksort sorts the array in place, without using additional lists (smaller_elements and larger_elements). It rearranges elements within the original array to partition around the pivot.

The real version

A closer version of quick sort would look like this:

class Main {

    public static void quicksort(int[] array, int start, int end) {
        if (end <= start) return; // Base case

        int pivot = partition(array, start, end);
        quicksort(array, start, pivot - 1);
        quicksort(array, pivot + 1, end);
    }

    public static int partition(int[] array, int start, int end) {
        int pivot = array[end];
        int i = start - 1;

        for (int j = start; j <= end - 1; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i]; // invert 2 variables
                array[i] = array[j];
                array[j] = temp;
            }
        }
        i++;
        int temp = array[i]; // invert 2 variables
        array[i] = array[end];
        array[end] = temp;

        return i; // location of the pivot
    }

    public static void displayArray(int[] array) {
        for (int i : array) {
            System.out.print(i);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{8, 2, 5, 3, 9, 4, 7, 6, 1};
        quicksort(array, 0, array.length - 1);
        displayArray(array);
    }
}

Alternatives

• Pivot selection: while choosing the first or last element as the pivot is a valid approach, it’s not the only one. The median-of-three method, which selects the median of the first, middle, and last elements, is often used to improve performance and reduce the chance of encountering worst-case scenarios.
• Two-pointer technique: classic quicksort does indeed use a two-pointer technique. One pointer starts at the beginning and the other at the end, moving towards each other to partition the array. This method can improve efficiency by reducing the number of swaps needed.

Complexity

The time complexity of quicksort can vary depending on how the pivot is chosen and the input array’s characteristics:

• Best case: O(n log n): this occurs when the pivot is chosen in such a way that it divides the array into two nearly equal halves each time.

• Average case: O(n log n): in most practical scenarios, quicksort performs close to its best case due to its efficient partitioning and divide-and-conquer approach.

• Worst case: O(n²): this happens when the pivot is chosen poorly, resulting in highly unbalanced partitions. An example is when the smallest or largest element is always chosen as the pivot, leading to unbalanced recursion.

Sources

• https://en.wikipedia.org/wiki/Quicksort
• https://www.baeldung.com/java-quicksort/