Understanding Quick Sort Algorithm (with Examples in Java)

Quick Sort is a popular sorting algorithm based on the Divide-and-Conquer approach, in which a problem is divided into smaller subproblems and solved individually, then the solutions to the individual subproblems are combined to get the final solution. In Quick Sort, the array is divided by selecting a partition element, the position from which we will divide the array. Before we divide the array, the position of the partition element is rearranged in such a way that it is placed before elements greater than it and after elements smaller than it. The left and right subarrays are further recursively divided in this manner until we reach a case where a subarray contains only one element. At this point, the array is already sorted. Working of Quick Sort Let's say we want to sort this array in ascending order. Step 1 We will start by selecting the pivot element. We can select the last element as the pivot: Step 2 Here we position the pivot element before elements greater than it and after elements smaller than it. To do that we will loop through the array and compare the pivot with all the elements preceding it. If we find an element greater than the pivot, we create a second pointer for it: If we find an element smaller than the pivot, we swap it with the second pointer: The process is repeated to set the next greater element as the second pointer, and swap it with an element smaller than the pivot if found: We will continue until we get to the end of the array: Once we are done comparing the elements and the elements smaller than the pivot have been moved to the right, we then swap the pivot with the second pointer: Step 3 Here we will divide the array according to the partition index. If we can represent the array as arr[start..end], then to divide the array by the partition we can get the left subarray as arr[start..partitionIndex-1] and the right subarray as arr[partitionIndex+1..end]. The subarrays are further divided in this way until each subarray contains only a single element: At this point, the array is already sorted. Implementation of Quick Sort public class QuickSortTest { public static void main(String[] args){ int[] arr = {8, 6, 2, 3, 9, 4}; System.out.println("Unsorted array: " + Arrays.toString(arr)); quickSort(arr, 0, arr.length-1); System.out.println("Sorted array: " + Arrays.toString(arr)); } public static int partition(int[] arr, int start, int end){ // set the last element as the pivot int pivot = arr[end]; // create a pointer for the next greater element int secondPointer = start-1; // move smaller elements to the left of the pivot for (int i = start; i < end; i++) { if(arr[i] < pivot){ secondPointer++; int temp = arr[i]; arr[i] = arr[secondPointer]; arr[secondPointer] = temp; } } // swap the pivot with the second pointer secondPointer++; int temp = arr[end]; arr[end] = arr[secondPointer]; arr[secondPointer] = temp; // return the partition position return secondPointer; } public static void quickSort(int[] arr, int start, int end){ if(start < end){ // divide the array into two sub arrays and get the partition index int partition = partition(arr, start, end); // recursively sort the two sub arrays quickSort(arr, start, partition - 1); quickSort(arr, partition + 1, end); } } } Let's look at the code above. The quickSort Method In the quickSort method, we first call the partition method to divide the array into two subarrays. We then recursively call quickSort on the left and right subarrays. This process continues until we reach a base condition where all subarrays contain only one element. At this point, the array is already sorted. The partition Method This is where we divide the into two subarrays. We start by setting pointers for the pivot and the next greater element. Then we loop through the array and move elements smaller than the pivot to the left. After that, we swap the pivot with the second pointer and return the partition position. Running the code above will print the following output to the console: Unsorted array: [8, 6, 2, 3, 9, 4] Sorted array: [2, 3, 4, 6, 8, 9] Time Complexity: Best Case (O(n log n)): Average Case (O(n log n)): Worst Case (O(n²)): Space Complexity O(n):

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // set the last element as the pivot
        int pivot = arr[end];
        // create a pointer for the next greater element
        int secondPointer = start-1;

        // move smaller elements to the left of the pivot
        for (int i = start; i < end; i++) {
            if(arr[i] < pivot){
                secondPointer++;
                int temp = arr[i];
                arr[i] = arr[secondPointer];
                arr[secondPointer] = temp;
            }
        }

        // swap the pivot with the second pointer
        secondPointer++;
        int temp = arr[end];
        arr[end] = arr[secondPointer];
        arr[secondPointer] = temp;

        // return the partition position
        return secondPointer;
    }

    public static void quickSort(int[] arr, int start, int end){
        if(start < end){
            // divide the array into two sub arrays and get the partition index
            int partition = partition(arr, start, end);

            // recursively sort the two sub arrays
            quickSort(arr, start, partition - 1);
            quickSort(arr, partition + 1, end);
        }
    }
}

Unsorted array: [8, 6, 2, 3, 9, 4]
Sorted array: [2, 3, 4, 6, 8, 9]

Related Posts

Jan 16, 2025

How to Get the Most out of Cursor

Jan 15, 2025

How to use an API: a tutorial for beginners!

Jan 17, 2025