# Quick Sort in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.

In quick sort, we first choose a `pivot` and divide into two sublists,one will contain elements `lower than pivot` and other will have elements `greater than pivot`.

## Quick sort Algorithm

Lets say array is arr[]

• Choose a `pivot`, it is generally mid element of the list.
• Initialise two index variable , `left=0` and `right=arr.length-1`
• Increment left variable until you get element higher than pivot.
• Decrement right variable until you get element lesser than pivot
• swap `arr[left]` and `arr[right]`
• `Recursively sort sublists`(sublist with less than pivot, sublist greater than pivot) using above algorithm.
• In the end , you will get `sorted array`.

## Quick Sort implementation

Output:

Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1]
==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]

## Time complexity

Best Case : `O(n log n)`
Average Case : `O(n log n)`
Worst Case : `O(n^2)`