Sorting (quicksort)
In this lecture, Prof Jonathan Shewchuk explains the Quicksort sorting algorithm, currently part of the Java library sort routine. Like various efficient sorting algorithms, including the mergesort used by the Java library, Quicksort is a recursive "divide and conquer" strategy.
Related pages on this site:
Sorting Java collections
Java sort algorithm
Java sort performance
Lecture overview
| Time | Notes / content / relevant pages on this site |
|---|---|
| 0'00 | Introduction to Quicksort and overview of algorithm |
| 15'00 | Choosing the pivot |
| 23'00 | Quicksort on linked lists: extracting equal keys |
| 28'40 | Comparison with mergesort |
| 29'20 | Problem with extracting equal keys with array sort |
| 30'25 | Choosing a random pivot with a linked list |
| 31'00 | Quicksort on arrays: in-place sorting |
| 41'00 | Dealing with keys the same as the pivot |