NUHMAN.com

1. Introduction to Quicksort

Quicksort is an efficient, 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 recursively sorted.

2. Quicksort Implementation in Java

Here’s a simple implementation of the Quicksort algorithm in Java:

java

public class QuickSort {

    // Main function that sorts an array using QuickSort
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(array, low, high);

            // Recursively sort elements before and after the partition
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    // Function to partition the array based on the pivot
    private static int partition(int[] array, int low, int high) {
        // Choose the rightmost element as pivot
        int pivot = array[high];

        // Pointer for the greater element
        int i = low - 1;

        // Traverse through all elements and compare with the pivot
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                // Swap elements at i and j
                swap(array, i, j);
            }
        }

        // Swap the pivot element with the element at i+1
        swap(array, i + 1, high);

        return i + 1;
    }

    // Function to swap two elements in the array
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // Main method to test the QuickSort algorithm
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;

        System.out.println("Original Array:");
        printArray(array);

        quickSort(array, 0, n - 1);

        System.out.println("\nSorted Array:");
        printArray(array);
    }

    // Utility function to print the array
    private static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

3. How It Works

• Partitioning: The partition method rearranges the elements in the array such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
• Recursion: The quickSort method recursively sorts the sub-arrays on either side of the pivot.
• Swapping: The swap method exchanges the elements in the array.

4. Example Execution

If you run the main method with the input array {10, 7, 8, 9, 1, 5}, the output will be:

javascript

Original Array:
10 7 8 9 1 5 

Sorted Array:
1 5 7 8 9 10

5. Time Complexity

• Best and Average Case: The time complexity is O(n log n), where n is the number of elements in the array.
• Worst Case: The time complexity is O(n^2), which happens when the pivot element is the smallest or largest element (e.g., in an already sorted array).

This implementation of Quicksort is in-place, meaning it doesn’t require extra space proportional to the input size, making it memory efficient.