# 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)

That’s all about quick sort in java.