Quicksort is a comparison sort based on divide and conquer algorithm. Quick sort is more fast in comparison to Merge Sort ot Heap Sort. It’s not required additional space for sorting.

How Quick Sort Works

The idea to implement Quicksort is first divides a large array into two smaller sub-arrays as the low elements and the high elements then recursively sort the sub-arrays.

The above process follow below steps:

1. If array having 0 or 1 item then it’s already sorted.
2. Pick an item from the array that is called as pivot.
3. Partition this array as items less than pivot will come before pivot while items greater than pivot will come after it (equals values can either way). Now Pivot get it’s exact position.
4. Now repeat step 2 and 3 for both left and right side values of Pivot and continue same as long as no left or right items remaining.
5. Finally, as result of array will sorted items.

Points to remember

• Data Structure: Array
• Best Time Complexity: Ω(n log(n))
• Time Complexity: Θ(n log(n))
• Worst Time Complexity: O(n^2)
• Worst Space Complexity: O(log(n))

Quick Sort Program

public class QuickSort {

public void quicksort(int[] array) {
quicksort(array, 0, array.length - 1);
}

private void quicksort(int[] array, int first, int last) {
if (first < last) {
int pivot = partition(array, first, last);

// Recursive call
quicksort(array, first, pivot - 1);
quicksort(array, pivot + 1, last);
}
}

private int partition(int[] input, int first, int last) {

//choose pivot as last item
int pivot = last;

swap(input, pivot, last);
for (int i = first; i < last; i++) {
if (input[i] <= input[last]) {
swap(input, i, first);
first++;
}
}

swap(input, first, last);
return first;
}

private void swap(int[] input, int a, int b) {
int temp = input[a];
input[a] = input[b];
input[b] = temp;
}

public static void printArray(int[] items) {
for (int i = 0; i < items.length; i++) {
System.out.print(items[i] + " ");
}
}

public static void main(String[] args) {

int[] items = {12, 24, 45, 56, 10, 9, 49, 30, 5, 15};
System.out.println("Original Array Before Quick Sort");
printArray(items);

System.out.println("\n\nAfter QuickSort");

QuickSort sort = new QuickSort();
sort.quicksort(items);
printArray(items);

}
}

Output

Original Array Before Quick Sort
12 24 45 56 10 9 49 30 5 15 

After QuickSort
5 9 10 12 15 24 30 45 49 56