Understand quicksort partitioning

The most important part of understanding quicksort is to understand the partitioning function.

Here is an intuitive way to present the array being currently partitioned, let’s say we’ve selected a pivot in the middle of the array and its value is 100. Here’s the array being partitioned.

Where pivot was prior to partitioning and after the partitioning doesn’t really matter, as long as it ends up being on the correct side of the result boundary.What really matters is that when partitioning is done, all elements to the left of left index are smaller than pivot.(or all elements to the right of right index are larger than pivot)Let’s assume the pivot element 100 has already been swapped to the blue part.

The left index keeps increasing, and all elements it left behind are smaller than the pivot. At the same time, the right index keeps decreasing, and all elements it left behind are larger than the pivot.
If left index meets an element larger than or equal to the pivot, it stops, and wait for right index to find an element smaller than or equal to the pivot, then they swap the elements and continue the step 1 until the left index is larger than the right index. What if the right index does not find an element smaller than or equal to the pivot? Then the right index will just continue moving to the left until it passes the left index, and stops at the next element of the left index (because its value is smaller than pivot). Then the partitioning is done.
return the left index as the boundary to which all elements on the left are smaller than the pivot.

import java.util.Arrays;

public class Solution {

    public void quicksort(int[] arr) {
        quicksort(arr, 0, arr.length - 1);
    }

    private void quicksort(int[] arr, int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1) {
            quicksort(arr, left, index - 1);
        }
        if (index < right) {
            quicksort(arr, index, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[(left + right) / 2];
        while (left <= right) {
            while (arr[left] < pivot) {
                left++;
            }
            while (arr[right] > pivot) {
                right--;
            }

            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        return left;
    }

    private void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 5, 7, 2, 1, 3 };
        Solution solution = new Solution();
        solution.quicksort(arr);
        // Array is sorted : [1, 2, 3, 5, 7]
        System.out.println(Arrays.toString(arr));
    }
}

Bonus: Have you seen this amusing Hungarian quicksort dance before?

Menu