Adam Hacks

CS Review: Quicksort

Quicksort is another one of the divide and conquer sorting algorithms. It works by partitioning the array around some chosen pivot point, which there are a few different ways to choose.

Quicksort is generally preferred over merge sort for sorting arrays due to the fact that the general form of the algorithm sorts in-place.

How Quicksort Works

As has already been mentioned, quicksort partitions your array of data based on some pivot point. As such, the big question becomes how to choose this pivot point. There are a few common ways that you’ll see:

Most practical implementations of the quicksort algorithm use the randomized approach, so that’s the one I’ll use for my implementation here.

As you’ll see, the partition method is the real key to the entire quicksort algorithm. This method will split the array based on our pivot point. It takes the pivot element and places it in the correct position in the sorted array, placing all smaller elements to the left of pivot and all larger elements to the right.

Implementation

As usual, I think this concept becomes the most clear when we take a look at the implementation, so here it is in Java:

 1package com.hackeradam.sorting;
 2import java.util.Random;
 3public class Main {
 4     // Helper function that swaps two items in an array
 5    public static void swap(int arr[], int i, int j) {
 6        int tmp = arr[i];
 7        arr[i] = arr[j];
 8        arr[j] = tmp;
 9    }
10    // Chooses a random pivot point for Quicksort
11    public static void randomPivot(int arr[], int low, int high) {
12        Random rand = new Random();
13        int pivot = rand.nextInt(high - low) + low;
14        swap(arr, pivot, high);
15    }
16    // Performs the partitioning for Quicksort
17    public static int partition(int arr[], int low, int high) {
18        // Choose a random pivot point
19        randomPivot(arr, low, high);
20        int pivot = arr[high];
21        int i = low - 1; // Tracks the index of the smaller element
22        for (int j = low; j < high; j++) {
23            // If current element < pivot, swap
24            if (arr[j] < pivot) {
25                swap(arr, ++i, j);
26            }
27        }
28        // Swap arr[i + 1] and pivot (high)
29        swap(arr, i+1, high);
30        return i+1;
31    }
32    // Performs a quicksort on an integer array
33    public static void quicksort(int arr[], int low, int high) {
34        if (low < high) {
35            int partition = partition(arr, low, high);
36            // Do the recursive sort of items left of partition
37            // and then items right of partition
38            quicksort(arr, low, partition-1);
39            quicksort(arr, partition+1, high);
40        }
41    }
42    // Helper to make calling quicksort easier
43    public static void quicksort(int arr[]) {
44        quicksort(arr, 0, arr.length-1);
45    }
46    public static void printArray(int arr[]) {
47        for (int i=0; i < arr.length; i++) {
48            System.out.print(arr[i] + " ");
49        }
50        System.out.println();
51    }
52    public static void main(String... args) {
53        int items[] = {5, 2, 88, 100, 3, 0, -1, 20, 30, 7, 99};
54        printArray(items);
55        System.out.println("After quicksort: ");
56        quicksort(items);
57        printArray(items);
58    }
59}

Time Complexity

The worst-case for quicksort occurs when our partition method always chooses either the smallest or largest item as the pivot point. The worst-case in this case turns out to be O(n2). The average case, however, turns out to be O(n log n).

It’s also worth mentioning that while quicksort has a worse worst-case time complexity compared to other algorithms, such as merge sort, it’s often faster in practice due to the optimizations that can occur to the inner loop of the algorithm. Additionally, it doesn’t require the O(n) extra space for sorting that merge sort requires.

#Computer-Science #Programming #Algorithms