CS210 · Sorting · Annotated SlidesQuick Sort
Original
Overview

Quick Sort

Quicksort: partitioning, the Java implementation, best/worst/average case, why we shuffle, duplicate keys, and how it compares with the other sorts.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 39 slides
  1. 1 A l g o r i t h m s
  2. 2 Two classic sorting algorithms: mergesort and quicksort
  3. 3 Quicksort t-shirt
  4. 4 Slide 4
  5. 5 ocntime
  6. 6 join
  7. 7 3 7 2 4 1 5 9
  8. 8 Tony Hoare
  9. 9 Tony Hoare
  10. 10 Bob Sedgewick
  11. 11 Quicksort partitioning demo
  12. 12 ABCDEFGHijklmnoparstuvwxyz.pivf.iq too
  13. 13 Quicksort partitioning demo
  14. 14 Quicksort: Java code for partitioning
  15. 15 Quicksort: Java implementation
  16. 16 Quicksort trace
  17. 17 Quicksort animation
  18. 18 Quicksort: implementation details
  19. 19 Quicksort: empirical analysis (1961)
  20. 20 Quicksort: empirical analysis
  21. 21 perfectly geg
  22. 22 sorted
  23. 23 Quicksort: average-case analysis
  24. 24 Quicksort: average-case analysis
  25. 25 Quicksort: average-case analysis
  26. 26 Quicksort: average-case analysis
  27. 27 Quicksort: average-case analysis
  28. 28 Quicksort: summary of performance characteristics
  29. 29 Quicksort properties
  30. 30 Slide 30
  31. 31 Duplicate keys
  32. 32 Duplicate keys
  33. 33 What is the result of partitioning the following array?
  34. 34 Partitioning an array with all equal keys
  35. 35 Duplicate keys: the problem
  36. 36 Sorting summary
  37. 37 System sort in Java 7
  38. 38 Slide 38
  39. 39 swap
Slide 1 / 39

A l g o r i t h m s

Slide 1: A l g o r i t h m s
Slide 2 / 39

Two classic sorting algorithms: mergesort and quicksort

Slide 2: Two classic sorting algorithms: mergesort and quicksort
Slide 3 / 39

Quicksort t-shirt

Slide 3: Quicksort t-shirt
Slide 4 / 39

Slide 4

Slide 4: Slide 4
Slide 5 / 39

ocntime

Slide 5: ocntime
Slide 6 / 39

join

Slide 6: join
Slide 7 / 39

3 7 2 4 1 5 9

Slide 7: 3 7 2 4 1 5 9
Slide 8 / 39

Tony Hoare

Slide 8: Tony Hoare
Slide 9 / 39

Tony Hoare

Slide 9: Tony Hoare
Slide 10 / 39

Bob Sedgewick

Slide 10: Bob Sedgewick
Slide 11 / 39

Quicksort partitioning demo

Slide 11: Quicksort partitioning demo

Notes

  1. Partition around a pivot: smaller items left, larger right; the pivot lands in its final place.

Exam angle

Slide 12 / 39

ABCDEFGHijklmnoparstuvwxyz.pivf.iq too

Slide 12: ABCDEFGHijklmnoparstuvwxyz.pivf.iq too
Slide 13 / 39

Quicksort partitioning demo

Slide 13: Quicksort partitioning demo
Slide 14 / 39

Quicksort: Java code for partitioning

Slide 14: Quicksort: Java code for partitioning
Slide 15 / 39

Quicksort: Java implementation

Slide 15: Quicksort: Java implementation

Notes

  1. Shuffle first, partition, then sort each part recursively.

Slide 16 / 39

Quicksort trace

Slide 16: Quicksort trace
Slide 17 / 39

Quicksort animation

Slide 17: Quicksort animation
Slide 18 / 39

Quicksort: implementation details

Slide 18: Quicksort: implementation details
Slide 19 / 39

Quicksort: empirical analysis (1961)

Slide 19: Quicksort: empirical analysis (1961)
Slide 20 / 39

Quicksort: empirical analysis

Slide 20: Quicksort: empirical analysis
Slide 21 / 39

perfectly geg

Slide 21: perfectly geg

Notes

  1. Best case: ~N lg N compares. Worst case (already sorted, no shuffle): ~N²/2.

Exam angle

PredictionQ1

Without shuffling, quicksort (first element as pivot) is slowest on:

Slide 22 / 39

sorted

Slide 22: sorted
Slide 23 / 39

Quicksort: average-case analysis

Slide 23: Quicksort: average-case analysis
Slide 24 / 39

Quicksort: average-case analysis

Slide 24: Quicksort: average-case analysis
Slide 25 / 39

Quicksort: average-case analysis

Slide 25: Quicksort: average-case analysis
Slide 26 / 39

Quicksort: average-case analysis

Slide 26: Quicksort: average-case analysis
Slide 27 / 39

Quicksort: average-case analysis

Slide 27: Quicksort: average-case analysis
Slide 28 / 39

Quicksort: summary of performance characteristics

Slide 28: Quicksort: summary of performance characteristics

Notes

  1. Average ~1.39 N lg N compares; in place; not stable.

Exam angle

PredictionQ1

Quicksort’s average running time is:

Slide 29 / 39

Quicksort properties

Slide 29: Quicksort properties
Slide 30 / 39

Slide 30

Slide 30: Slide 30
Slide 31 / 39

Duplicate keys

Slide 31: Duplicate keys
Slide 32 / 39

Duplicate keys

Slide 32: Duplicate keys
Slide 33 / 39

What is the result of partitioning the following array?

Slide 33: What is the result of partitioning the following array?
Slide 34 / 39

Partitioning an array with all equal keys

Slide 34: Partitioning an array with all equal keys
Slide 35 / 39

Duplicate keys: the problem

Slide 35: Duplicate keys: the problem
Slide 36 / 39

Sorting summary

Slide 36: Sorting summary

Notes

  1. Summary: selection n²/2, insertion n²/4 average, merge N lg N (stable, extra space), quick 1.39 N lg N (in place, fastest in practice).

Slide 37 / 39

System sort in Java 7

Slide 37: System sort in Java 7
Slide 38 / 39

Slide 38

Slide 38: Slide 38
Slide 39 / 39

swap

Slide 39: swap