Quick sort | java

 Quick sort | java 

Quick sort is a highly efficient sorting algorithm based on the divide-and-conquer strategy. 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.

Code:

public class quickSort {

    public static void quicksrt(int arr[], int si, int ei) {

        

        if (si >= ei) {

            return; // base case for recurtion;

        }

        int pIdx = partition(arr, si, ei);

        quicksrt(arr, si, pIdx - 1); // left

        quicksrt(arr, pIdx + 1, ei); // left

    }

    public static int partition(int arr[], int si, int ei) {

        int pivot = arr[ei];

        int i = si - 1; // to make a place for swap ele

        for (int j = si; j < ei; j++) {

            if (arr[j] <= pivot) {

                i++;

                // swap

                int tmp = arr[j];

                arr[j] = arr[i];

                arr[i] = tmp;

            }

        }

        i++;

        int temp = pivot;

        arr[ei] = arr[i];

        arr[i] = temp;

        return i;

    }

    public static void main(String[] args) {

        int arr[] = { 7, 6, 5, 1, 2, 3, 4 };

        quicksrt(arr, 0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {

            System.out.println(arr[i]);

        }

    }

}

output:

1

2

3

4

5

6

7

Here's a brief explanation of the provided code:

1. `quicksrt()` method:

   - This method is the entry point for the quick sort algorithm.

   - It takes three parameters: the array to be sorted (`arr`), the start index (`si`), and the end index (`ei`) of the array segment to be sorted.

   - It checks for the base case where the start index is greater than or equal to the end index. If this condition is met, it returns, indicating that the array segment is already sorted.

   - It finds the partition index using the `partition()` method.

   - It recursively applies the quick sort algorithm to the left and right segments of the array.

2. `partition()` method:

   - This method takes three parameters: the array to be partitioned (`arr`), the start index (`si`), and the end index (`ei`) of the array segment to be partitioned.

   - It selects the pivot element, which is the last element of the array segment (`arr[ei]`).

   - It initializes an index `i` to `si - 1`.

   - It iterates through the array segment from the start index to the end index - 1.

   - For each element `arr[j]`, if it is less than or equal to the pivot, it increments `i` and swaps `arr[i]` with `arr[j]`.

   - After the loop, it increments `i` once more and swaps `arr[i]` with the pivot element.

   - It returns the partition index `i`.

3. `main()` method:

   - This method initializes an array `arr`.

   - It calls the `quicksrt()` method to sort the array.

   - Finally, it prints the sorted array.

The key idea behind quick sort is the partitioning step, which rearranges the elements of the array in such a way that elements less than the pivot are on one side and elements greater than the pivot are on the other side. This process is repeated recursively on the left and right sub-arrays until the entire array is sorted.