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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
package org.arpit.java2blog; import java.util.Arrays; public class QuickSortMain { private static int array[]; public static void sort(int[] arr) { if (arr == null || arr.length == 0) { return; } array = arr; quickSort(0, array.length-1); } private static void quickSort(int left, int right) { int i = left; int j = right; // find pivot number, we will take it as mid int pivot = array[left+(right-left)/2]; while (i <= j) { /** * In each iteration, we will increment left until we find element greater than pivot * We will decrement right until we find element less than pivot */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchange(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (left < j) quickSort(left, j); if (i < right) quickSort(i, right); } private static void exchange(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String a[]){ int[] input = {33,21,45,64,55,34,11,8,3,5,1}; System.out.println("Before Sorting : "); System.out.println(Arrays.toString(input)); sort(input); System.out.println("=================="); System.out.println("After Sorting : "); System.out.println(Arrays.toString(array)); } } |

**Output:**

[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)`

To understand more about complexity,please go through complexity of algorithm.