Quicksort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Animated visualization of the quicksort algorithm. The horizontal lines are pivot values

Quicksort is a sorting algorithm that is used to sort elements in an array. It was created by Tony Hoare in 1959[1], and it is still widely used today. Quicksort creates partitions within the array, essentially meaning that it splits the array into two parts, and then continues to split those parts into more parts, and sorting along the way. It does the actual sorting by nature of it being a comparison sort. This means that it chooses a pivot point in the array, and then compares it with all the other points in the array.

Algorithm[change | change source]

  1. Pick any element in the array, this will now be the pivot point.
  2. Partition the elements. Compare all the elements in the array to the pivot, those that are lower than the pivot are moved to the left of the pivot, and all the elements in the array that are higher than the pivot are moved to the right of the pivot. Note that our pivot is now in its sorted position.
  3. Recurse into the two partitions. Apply the above two steps to the two partitions we created in step 2.

Often the leftmost element is chosen as the pivot. The recursion means that the algorithm runs the same exact algorithm on the two partitions that were created by the comparisons to the pivot. Note that this algorithm will keep on partitioning the array into subarrays, and splitting those subarrays into even smaller subarrays. Each time it does this, it will choose a new pivot within the subarray and compare the elements to the subarray. The base case is when the algorithm reaches a subarray with only one element, in which it just stops because one element does not need to be sorted.

References[change | change source]

  1. "Sir Antony Hoare | Computer History Museum". web.archive.org. 2015-04-03. Retrieved 2019-02-25.