Quicksort uses divide and conquer technique to provide fast sorting.


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.

quicksort

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

Javascript

Python

Doodle

quick sort 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?

quick sort

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). It is used for recursion’s call stacks.