QuickSort algorithm

Category : Data-structures-algorithms | Sub Category : QuickSort algorithm | By Prasad Bonam Last updated: 2023-07-10 04:39:08 Viewed : 325

QuickSort algorithm :

Here is an example of the QuickSort algorithm implemented in Java:

javaCopy code
public class QuickSort {
    
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    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++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 8, 5, 2, 9, 1, 6, 3, 7 };
        System.out.println("Original array: " + Arrays.toString(arr));
        
        quickSort(arr);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

In the quickSort method, we define the base case where the low index is less than the high index. If the base case is satisfied, we select a pivot element (here, we choose the rightmost element as the pivot) and partition the array around it using the partition method. The partition method moves elements smaller than the pivot to the left side of the array, and larger elements to the right side. Then, the quickSort method is called recursively for the left and right subarrays.

The partition method selects a pivot and iterates over the array, swapping elements smaller than the pivot to the left side. Finally, it places the pivot in its correct position, and returns the pivot index.

In the main method, we demonstrate the usage of the QuickSort algorithm by sorting an example array. The original array is printed before sorting, and the sorted array is printed afterward.

The QuickSort algorithm has an average time complexity of O(n log n) and performs in-place sorting.