This lesson introduces quicksort, its central idea, and why it became a widely used sorting algorithm.
Quicksort sorts a range by choosing a value called a pivot and rearranging the other values around it. Values less than the pivot go to one side; values greater than it go to the other. The resulting subranges are then sorted recursively.
For example, with the values [7,2,5,1,8], choosing 5 as a pivot allows the values below 5 to be grouped on one side and values above 5 on the other. The subranges can then be sorted independently. The exact arrangement depends on the partition method.
All flashcards
What is quicksort?
A comparison-based, divide-and-conquer sorting algorithm that partitions a range around a pivot and recursively sorts the resulting ranges.
What is a pivot in quicksort?
A value selected from the range being sorted to guide its partition into smaller ranges.
What does in-place quicksort mean?
It rearranges values within the original array and uses little additional partitioning storage, apart from its recursion stack.
Is ordinary in-place quicksort stable?
Usually not; equal items are not guaranteed to retain their original relative order.
Who developed quicksort, and when?
Tony Hoare developed it in 1959 and published an improved recursive version in 1961.
Quiz questions
What does median-of-three pivot selection do?Answer: It selects the median of the first, middle, and last values.
How does three-way partitioning help when many values are equal?Answer: It groups values below, equal to, and above the pivot, then skips the equal group during recursion.
How does introsort limit quicksort's worst-case running time?Answer: It switches to heapsort when recursion becomes too deep or a poor case is detected.
What is quickselect designed to find?Answer: An item at a specified rank, such as the kth-smallest value.
Which combination describes array-based merge sort?Answer: It is stable, runs in O(nlogn) worst-case time, and generally needs O(n) auxiliary storage.
Based on the Wikipedia article Quicksort, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.