## QuickSort algorithm

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

QuickSort algorithm :

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

```javapublic 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.