- Like Merge Sort, Quick Sort is also a Divide and Conquer algorithm.
- It picks an element as pivot and partitions the given array around the picked pivot.
- There are many different versions of quickSort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot.
- Always pick middle element as pivot.
The key process in quickSort is partition().
Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
Quick sort Algorithm:
- 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.
import java.util.Arrays;
public class QuickSort2 {
private static int array[];
public static void main(String a[]) {
int[] input = { 0, 9, 1, 8, 2, 7, 3, 6, 4, 5 };
// { 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
// { 15, 9, 7, 13, 12, 16, 4, 18, 11 };
// { 10, 80, 60, 90, 40, 30, 70 };
// { 33, 21, 45, 64, 55, 34, 90 };
// { 15, 9, 7, 13, 12, 16, 4, 18, 11 };
// { 90, 23, 101, 45, 65, 23, 67, 89, 34, 23 };
// {1,4,45,33,21,45,64,55,34,11,8,3,5,1,34,45,23,7,87,3,92,0};
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));
}
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 low = left;
int high = right;
// find pivot number, we will take it as mid
int pivot = array[(left + right) / 2];
while (left <= right) {
/**
* 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[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left <= right) {
exchange(left, right);
// move index to next position on both sides
left++;
right--;
}
}
// call quickSort() method recursively.
// If low is still less than right, i.e if right while decrementing has
// not been less than low, then again call quicksort.
if (low < right)
quickSort(low, right);
// If high is still greater than lft, i.e if left while incrementing has
// not been greater than high, then again call quicksort.
if (high > left)
quickSort(left, high);
}
private static void exchange(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Output: Before Sorting : [0, 9, 1, 8, 2, 7, 3, 6, 4, 5] After Sorting : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Complexity:
| Complexity | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Time Complexity | O(n) for 3 way partition or O(n log n) simple partition | O(n log n) | O(n2) |
| Space Complexity | O(log n) |
Harshit Jain 