Efficient QuickSort Divide-and-Conquer Algorithm

Introduction

QuickSort is a Divide-and-Conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. QuickSort's average case complexity is O(n log n). It should be noted that QuickSort is not a stable sort, that is, the relative positions of equal sort items may not be preserved.

Skills Graph

Import the Arrays Class

In this step, you need to import the java.util.Arrays class. This class contains several methods for manipulating arrays that will be used to convert the int arrays to Strings.

import java.util.Arrays;

Define the partition() method

Define a helper method named partition(). The partition() method will take an array arr, a starting index low, and an ending index high as input. The partition() method will select an element as a pivot, and partition the elements such that all elements less than the pivot element are to the left of the pivot, and all elements greater than the pivot are to the right of the pivot. The pivot element will be placed in its correct position.

The partition() method will return the index of the partitioned element. The partitioned element is the position where the pivot element is placed.

public static int partition(int[] arr, int low, int high) {
    // Select the pivot element
    int pivot = arr[high];
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // increment index of smaller element
            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // swap arr[i + 1] and arr[high]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1; // Return the partition index
}

Define the quicksort() method

Define a sorting method named quicksort(). The quicksort() method will take an array arr, a starting index low, and an ending index high as input. The quicksort() method will recursively sort the arr[] array.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[p] is now
        // at right place
        int pi = partition(arr, low, high);

        // Recursively sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Create and Assign an Integer Array

Create and assign integer arrays to be sorted to the arr field.

int[] arr = {7, 9, 1, 2, 10, 15, 6};

Implement QuickSort

Call the quickSort() method with the arr field as input, along with the initial and final index of the array. Sort and display the array using the Arrays.toString(arr) method.

quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));

Test With Multiple Arrays

Test your QuickSort implementation using arrays with various traits.

int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};

quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);

System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));

Randomly Select the Pivot

In this step, we need to randomly select the pivot on each iteration to avoid the worst-case scenario. To achieve this we will update the partition() method and replace the following line:

int pivot = arr[high];

with this line:

int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;

Test with Randomized Pivot Element

Test your QuickSort implementation using randomized pivot elements.

int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};

quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);

System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));

Handle Edge Cases

In this step, we will cover edge cases that QuickSort can handle. Define these edge cases as integer arrays.

int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);

System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));

Complete Code

The complete code of the QuickSort in Java Lab is given below.

import java.util.Arrays;

public class QuickSort {

    public static int partition(int[] arr, int low, int high) {
        int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
        int pivot = arr[pivotIndex];
        arr[pivotIndex] = arr[high];
        arr[high] = pivot;
        int i = low - 1;
        for (int j = low; j <= high - 1; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }

    public static void main(String[] args) {
        System.out.println("Quick Sort Implementation in Java\n-----------------------");
        int[] arr = {7, 9, 1, 2, 10, 15, 6};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
        int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] arr3 = {1};
        int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};

        quickSort(arr1, 0, arr1.length-1);
        quickSort(arr2, 0, arr2.length-1);
        quickSort(arr3, 0, arr3.length-1);
        quickSort(arr4, 0, arr4.length-1);

        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
        System.out.println(Arrays.toString(arr3));
        System.out.println(Arrays.toString(arr4));

        int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
        int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
        int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
        int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};

        quickSort(arr5, 0, arr5.length-1);
        quickSort(arr6, 0, arr6.length-1);
        quickSort(arr7, 0, arr7.length-1);
        quickSort(arr8, 0, arr8.length-1);

        System.out.println(Arrays.toString(arr5));
        System.out.println(Arrays.toString(arr6));
        System.out.println(Arrays.toString(arr7));
        System.out.println(Arrays.toString(arr8));

        int[] arr9 = {};
        int[] arr10 = {1, 1, 1, 1};
        int[] arr11 = {1};
        quickSort(arr9, 0, arr9.length-1);
        quickSort(arr10, 0, arr10.length-1);
        quickSort(arr11, 0, arr11.length-1);

        System.out.println(Arrays.toString(arr9));
        System.out.println(Arrays.toString(arr10));
        System.out.println(Arrays.toString(arr11));
    }
}

Summary

This lab provided a step-by-step guide to implementing the QuickSort algorithm in Java. We learned that pivoting is a crucial step in QuickSort and that different techniques for selecting a pivot can affect the performance of the algorithm. Quicksort is best used for sorting large amounts of data. The worst-case time complexity of QuickSort is O(N^2), while its average and best-case time complexity is O(NLogN).