Quick Sort Algorithm in Java

1. Introduction

Quick Sort is a divide-and-conquer algorithm that 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. With an average time complexity of O(n log n), Quick Sort is one of the fastest sorting algorithms available for large datasets.

2. Implementation Steps

1. Choose a 'pivot' element from the array.

2. Partition the array around the pivot, such that elements less than the pivot come before it and elements greater than the pivot come after.

3. Recursively apply the above two steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

4. The base case of the recursion is when the size of the array is zero or one, at which point the array is returned as it is since it's already sorted.

3. Implementation in Java

public class QuickSort {
    // Function to partition the array
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; 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;
    }
    // QuickSort function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    // Function to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Original array:");
        printArray(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output:

Original array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10

Explanation:

1. The partition function is the heart of Quick Sort. It selects a pivot element and then rearranges the array such that elements less than the pivot come before it, and elements greater than the pivot come after.

2. In this function, the pivot is chosen as the last element. This is a simple approach but other strategies like median-of-three can be used to select the pivot.

3. The quickSort function is the recursive function that applies the partitioning and then sorts the two resulting sub-arrays.

4. Elements are swapped in the partition function to achieve the desired partitioning around the pivot.

5. The main function demonstrates the use of quickSort with a sample array. It prints the array before and after sorting.