How to implement Quick Sort in java

# How to implement Quick Sort in java

Quick sort which by name conveys sorting done quickly. It is based on Divide and Conquer as termed as Partition exchange sort. Though this sorting algorithm is not stable but it requires very less additional space and is fast. To follow its definition of divide and conquer, it first selects a pivot value and with the assistance of Pivot value list is splitting into three parts as mentioned below-

1. Elements lesser than Pivot value
2. Pivot Value
3. Elements greater than Pivot value

There are many ways to choose the pivot value, but generally middle index item in list selected as pivot value. The actual position of pivot value in final sorted list is called a splitting point.

Worst Case Time Complexity : O(n2)

Best Case Time Complexity : O(n log n)

Average Time Complexity : O(n log n)

Space Complexity : O(n log n)

Space required by quick sort is very less, only O(n log n) additional space is required.

Quick sort is not a stable sorting technique, so it might change the occurrence of two similar elements in the list while sorting.

Let’s see an example-

```package com.code2succeed.sorting;
import java.util.Arrays;
public class QuickSort{
public static void main(String args[]) {

// unsorted array with integer elements
int[] unsortedarray = {15, 14, 12, 10, 17, 16, 11, 13};
System.out.println("Unsorted array :" + Arrays.toString(unsortedarray));
QuickSortArray algorithm = new QuickSortArray(); // Sort integer array using QuickSortArray algorithm
algorithm.sort(unsortedarray); // Print sorted array
System.out.println("Sorted array :" + Arrays.toString(unsortedarray));
}
}

// QuickSortArray defined here
class QuickSortArray {
private int input[];
private int length;
public void sort(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return;
}
this.input = numbers;
length = numbers.length;
quickSort(0, length - 1);
}
private void quickSort(int low, int high) {
int i = low;
int j = high;
// Select pivot element at middle index
int pivot = input[low + (high - low) / 2]; // Split given array into two arrays

while (i <= j) {

while (input[i] < pivot) {
i++;
}
while (input[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++; j--; // move index to next position on both sides
}
} // Recursively call quickSort() method

if (low < j) {
quickSort(low, j);
}
if (i < high) {
quickSort(i, high);
}
}
private void swap(int i, int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}

}
```

Output

```Unsorted array :[15, 14, 12, 10, 17, 16, 11, 13]
Sorted array :[10, 11, 12, 13, 14, 15, 16, 17]```