## Thursday, May 5, 2022

### Question 82 : Implement quick sort in java?

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`.

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

``````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:

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

Don't miss the next article!

Be the first to be notified when a new article or Kubernetes experiment is published.