Quicksort uses divide and conquer technique to provide fast sorting. Divide-and-conquer is a technique works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
How quicksort works
First the sorting method calls a partition method to divide the array into two subarrays. This method returns an index for partition. Then the sorting method calls itself twice to sort these two subarrays.
The key part of the solution is the partition method. The variable pivot determines when to swap unordered elements. Its initial value can be the first, last or the middle item in the subarray. In this solution, the pivot is the middle of the array. The formula of its index is mid=low+(high-low)/2.
There are two pointers, low points to the first element. high points to the last element. Increase the low pointer if the values it points are less than the pivot. Decrease the high pointer if the values are larger than the pivot. After moving the pointers, if the low pointer is still less equal than the high pointer, swap the elements in the array. After each partition, either the largest element swaps to the right, or the smallest element swaps to the left.
Quicksort implementation
Java
|
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 |
import java.util.Arrays; public class QuickSort { //Divide and conquer, Time worst O(n^2) average O(n*logn), Space O(logn), n is array length public static void quickSort(int[] a, int low, int high) { int index = partition(a, low, high); if (low < index-1) quickSort(a, low, index-1); if (index < high) quickSort(a, index, high); } //Partition, Time O(n), Space O(1) private static int partition(int[] a, int low, int high) { int mid = low + (high-low)/2; //middle of the array int pivot = a[mid]; while (low <= high) { while (a[low] < pivot) low ++; while (a[high] > pivot) high --; if (low <= high) { swap(a, low, high); low ++; high --; } } return low; } //Swap two elements by index, Time O(1), Space O(1) private static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { int[] a = {19, 33, 4 , 61, 5, 38, -36, 21, 0}; quickSort(a, 0, a.length-1 ); System.out.print("Quick sort: "); System.out.println(Arrays.toString(a)); } } |
Javascript
|
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 |
//Divide and conquer, Time worst O(n^2) average O(n*logn), Space O(logn), n is array length function quickSort(a, low, high) { var index = partition(a, low, high); if (low < index-1) quickSort(a, low, index-1); if (index < high) quickSort(a, index, high); } //Partition, Time O(n), Space O(1) function partition(a, low, high) { var mid = Math.floor(low + (high-low)/2); //middle of the array var pivot = a[mid]; while (low <= high) { while (a[low] < pivot) low ++; while (a[high] > pivot) high --; if (low <= high) { swap(a, low, high); low ++; high --; } } return low; } //Swap two elements by index, Time O(1), Space O(1) function swap(a, i, j) { var tmp = a[i]; a[i] = a[j]; a[j] = tmp; } var a = [19, 33, 4 , 61, 5, 38, -36, 21, 0]; quickSort(a, 0, a.length-1 ); console.log("Quick sort: " + a); |
Python
|
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 |
#Divide and conquer, Time worst O(n^2) average O(n*logn), Space O(logn), n is array length def quickSort(a, low, high): index = partition(a, low, high) if low < index-1: quickSort(a, low, index-1) if index < high : quickSort(a, index, high) #Partition, Time O(n), Space O(1) def partition(a, low, high) : mid = int(low + (high-low)/2) #middle of the array pivot = a[mid] while (low <= high) : while (a[low] < pivot) : low += 1 while (a[high] > pivot): high -= 1 if (low <= high) : swap(a, low, high) low += 1 high -= 1 return low #Swap two elements by index, Time O(1), Space O(1) def swap(a, i, j) : tmp = a[i] a[i] = a[j] a[j] = tmp a = [19, 33, 4 , 61, 5, 38, -36, 21, 0] print(a) quickSort(a, 0, len(a)-1 ) print("Quick sort: ") print(a) |
Doodle
Download
Download quicksort in Java, JavaScript and Python
View how quicksort works
Sorting doodles compilation (YouTube)
What is the difference between quicksort and quickselect?
Quicksort is a sorting algorithm. Quickselect is an algorithm to find the kth smallest element in an unordered list. Similar to quicksort, it chooses one element as a pivot and partition data based on the pivot. This reduces the time complexity from O(nlogn) to average O(n).
What is the time complexity of quicksort?
Quicksort operates in O(nlogn) time. It is faster than simple sorting such as bubble sort, selection sort and insertion sort. The space complexity is O(logn). The space is used for recursion’s call stacks.