# Quick Sort algorithm

QuickSort is a Divide and Conquer algorithm having an average O(n log n) time complexity, it's one of the most used sorting algorithms, especially in sort() functions of almost all programming language's library.

Quick Sort is an in-place and non-stable sorting algorithm that takes constant O(1) auxiliary space.

Being a divide-and-conquer algorithm, in quick sort the input array is divided into two sub-arrays recursively based on an element called pivot; partition happens in such a way that elements smaller than the pivot are to the left and elements greater than the pivot are to the right.

## Quick Sort algorithm

In each pass one element finds its right place in the array at position pIndex, we further divide two subarrays with element left to sorted element at pIndex and to the right, utill all elements are sorted (sub array has one element left).
``````
Pass [1]
7, 2, 1, 6, 2, 5, 3, 4
pivot = 4, pIndex=0, i=1
a[i]<pivot (2<4)
swap (a[i],a[pIndex])
pIndex++

2, 7, 1, 6, 2, 5, 3, 4
pivot = 4, pIndex=1, i=2
a[i]<pivot (1<4)
swap (a[i],a[pIndex])
pIndex++

2, 1, 7, 6, 2, 5, 3, 4
pivot = 4, pIndex=2, i=3
a[i]>pivot (6>4)
No Swap, No increment in pIndex

2, 1, 7, 6, 2, 5, 3, 4
pivot = 4, pIndex=2, i=4
a[i]<pivot (2<4)
swap (a[i],a[pIndex])
pIndex++

2, 1, 2, 6, 7, 5, 3, 4
pivot = 4, pIndex=3, i=5
a[i]>pivot (5>4)
No Swap, No increment in pIndex

2, 1, 2, 6, 7, 5, 3, 4
pivot = 4, pIndex=3, i=6
a[i]<pivot (3<4)
swap (a[i],a[pIndex])
pIndex++

2, 1, 2, 3, 7, 5, 6, 4
pivot = 4, pIndex=4, i=7
(i<7 condition fails) Loop exits
swap(a[pIndex], a[7]) - Element at pIndex to be swapped with pivot (4-7)

2, 1, 2, 3, 4, 5, 6, 7
[2,1,2,3] [4] [5,6,7]
``````
Here 4 is already sorted and on its right place in sorted order, now same process will be followed for arrays [2,1,2,3] and [5,6,7].

## Quick Sort Implementation in Java

Here is the code for Quick Sort Implementation in Java, we have created a method quickSort(), it runs in recursion until the sub arrays has more than one element.

If input array has more than one element, a partition index in determined so that the element at returned index is already sorted, now sort() is called for remainig part of the sub arrays untill sub array has one element left.

In partition() method we pass array and start end position to determone sub array, we loop teh array from start to end-1, with start pIndex=0 and pivot as element at end position now the logic is, if a[i]<pivot than swap (a[i],a[pIndex]) and increment pIndex with one else do nothing.

Once loop is over, replace pivot (end element) with element at pIndex and return pIndex.
```package com.tb.arrays.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class QuickSort {
static int[] input = { 7, 2, 1, 6, 2, 5, 3, 4 };

private static void quickSort(int[] input, int start, int end) {
if (start < end) {
int pIndex = partition(input, start, end);
quickSort(input, start, pIndex - 1);
quickSort(input, pIndex + 1, end);
}
}

private static int partition(int[] input, int start, int end) {

int pivot = input[end];
int pIndex = start;

for (int i = start; i < end; i++) {
if (input[i] <= pivot) {
int tmp = input[i];
input[i] = input[pIndex];
input[pIndex] = tmp;
pIndex++;
}
}
int tmp = input[end];
input[end] = input[pIndex];
input[pIndex] = tmp;
System.out.println(printArrays(input) + ", pivot:" + pivot + ", pIndex:" + pIndex);
return pIndex;
}

private static String printArrays(int[] input) {
return Arrays.stream(input).mapToObj(String::valueOf).collect(Collectors.joining(", "));

}

public static void main(String[] args) {
System.out.println("Array before sort: " + printArrays(input));
quickSort(input, 0, input.length - 1);
System.out.println("Array after sort: " + printArrays(input));
}
}
```
Output: Output of above code will be something like this.
``````
Array before sort: 7, 2, 1, 6, 2, 5, 3, 4
Array after sort: 1, 2, 2, 3, 4, 5, 6, 7
``````
In this article we have seen "What is Quick sort?", Quick sort time complexity, usage and how to implemet Quick sort algorithm in Java.