CS210 · Sorting · Annotated SlidesElementary Sorting Algorithms
Original
Overview

Elementary Sorting Algorithms

Sorting with callbacks (Comparable), selection sort and insertion sort: inner loops, Java code, animations, and their compare and exchange counts.

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 32 slides
  1. 1 A l g o r i t h m s
  2. 2 Slide 2
  3. 3 Sorting problem
  4. 4 Sorting applications
  5. 5 Total order
  6. 6 Callbacks
  7. 7 Callbacks: roadmap
  8. 8 IG
  9. 9 Implementing the Comparable interface
  10. 10 Slide 10
  11. 11 s.im I
  12. 12 unsorted
  13. 13 selectthe
  14. 14 Two useful sorting abstractions
  15. 15 Selection sort inner loop
  16. 16 Selection sort: Java implementation
  17. 17 Selection sort: animations
  18. 18 Selection sort: animations
  19. 19 Selection sort: mathematical analysis
  20. 20 Slide 20
  21. 21 iWs
  22. 22 Insertion sort
  23. 23 Insertion sort inner loop
  24. 24 Insertion sort: Java implementation
  25. 25 Insertion sort: animation
  26. 26 Insertion sort: animation
  27. 27 Insertion sort: animation
  28. 28 Insertion sort: mathematical analysis
  29. 29 Insertion sort: trace
  30. 30 Insertion sort: analysis
  31. 31 9 casserarue
  32. 32 Insertion sort: practical improvements
Slide 1 / 32

A l g o r i t h m s

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

Slide 2

Slide 2: Slide 2
Slide 3 / 32

Sorting problem

Slide 3: Sorting problem
Slide 4 / 32

Sorting applications

Slide 4: Sorting applications
Slide 5 / 32

Total order

Slide 5: Total order
Slide 6 / 32

Callbacks

Slide 6: Callbacks
Slide 7 / 32

Callbacks: roadmap

Slide 7: Callbacks: roadmap
Slide 8 / 32

IG

Slide 8: IG
Slide 9 / 32

Implementing the Comparable interface

Slide 9: Implementing the Comparable interface
Slide 10 / 32

Slide 10

Slide 10: Slide 10
Slide 11 / 32

s.im I

Slide 11: s.im I
Slide 12 / 32

unsorted

Slide 12: unsorted
Slide 13 / 32

selectthe

Slide 13: selectthe
Slide 14 / 32

Two useful sorting abstractions

Slide 14: Two useful sorting abstractions
Slide 15 / 32

Selection sort inner loop

Slide 15: Selection sort inner loop

Notes

  1. Selection sort: find the minimum of the rest, swap it into position i.

Exam angle

Slide 16 / 32

Selection sort: Java implementation

Slide 16: Selection sort: Java implementation
Slide 17 / 32

Selection sort: animations

Slide 17: Selection sort: animations
Slide 18 / 32

Selection sort: animations

Slide 18: Selection sort: animations
Slide 19 / 32

Selection sort: mathematical analysis

Slide 19: Selection sort: mathematical analysis

Exam angle

PredictionQ1

Selection sort on an already sorted array takes:

Slide 20 / 32

Slide 20

Slide 20: Slide 20
Slide 21 / 32

iWs

Slide 21: iWs
Slide 22 / 32

Insertion sort

Slide 22: Insertion sort

Notes

  1. Insertion sort: move element i left past every larger element.

Slide 23 / 32

Insertion sort inner loop

Slide 23: Insertion sort inner loop
Slide 24 / 32

Insertion sort: Java implementation

Slide 24: Insertion sort: Java implementation
Slide 25 / 32

Insertion sort: animation

Slide 25: Insertion sort: animation
Slide 26 / 32

Insertion sort: animation

Slide 26: Insertion sort: animation
Slide 27 / 32

Insertion sort: animation

Slide 27: Insertion sort: animation
Slide 28 / 32

Insertion sort: mathematical analysis

Slide 28: Insertion sort: mathematical analysis

Notes

  1. Insertion sort: best case (sorted) ~n compares; worst (reverse) ~n²/2; average ~n²/4.

Exam angle

PredictionQ1

Which elementary sort runs in linear time on an already sorted array?

Slide 29 / 32

Insertion sort: trace

Slide 29: Insertion sort: trace
Slide 30 / 32

Insertion sort: analysis

Slide 30: Insertion sort: analysis
Slide 31 / 32

9 casserarue

Slide 31: 9 casserarue
Slide 32 / 32

Insertion sort: practical improvements

Slide 32: Insertion sort: practical improvements