CS210 · Annotated SlidesSorting — Elementary Sorting Algorithms
Sorting · Annotated slides

Elementary Sorting Algorithms

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

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: A l g o r i t h m s
Exam weight Low
    Slide 2: Slide 2
    Exam weight Low
      Slide 3: Sorting problem
      Exam weight Low
        Slide 4: Sorting applications
        Exam weight Low
          Slide 5: Total order
          Exam weight Low

            Callbacks

            Goal. Sort any type of data (for which sorting is well defined).

            Q. How can sort

            know how to compare data of type Double String

            ,

            , and

            without any information about the type of an item's key?

            java.io.File Callback = reference to executable code.

            ・

            Client passes array of objects to sort

            function.

            ・

            The sort

            function calls object's compareTo

            method as needed.

            Implementing callbacks.

            Java: interfaces.

            ・ ・

            C: function pointers.

            C++: class-type functors.

            ・ ・

            C#: delegates.

            ・

            Python, Perl, ML, Javascript: first-class functions.

            6
            Exam weight Low
              Slide 7: Callbacks: roadmap
              Exam weight Low
                Slide 8: IG
                Exam weight Low
                  Slide 9: Implementing the Comparable interface
                  Exam weight Low
                  1. Sort any type that implements Comparable (compareTo).
                  Slide 10: Slide 10
                  Exam weight Low
                    Slide 11: s.im I
                    Exam weight Low
                      Slide 12: unsorted
                      Exam weight Low
                        Slide 13: selectthe
                        Exam weight Low
                          Slide 14: Two useful sorting abstractions
                          Exam weight Low
                            Slide 16: Selection sort: Java implementation
                            Exam weight Low
                              Slide 17: Selection sort: animations
                              Exam weight Low
                                Slide 18: Selection sort: animations
                                Exam weight Low
                                  Slide 19: Selection sort: mathematical analysis
                                  Exam weight High
                                  1. Selection sort: ~n²/2 compares and n exchanges, regardless of input order.
                                  🎯 How this can come up · 1 question
                                  MCQ

                                  Selection sort on an already sorted array takes:

                                  Slide 20: Slide 20
                                  Exam weight Low
                                    Slide 21: iWs
                                    Exam weight Low
                                      Slide 22: Insertion sort
                                      Exam weight Low
                                      1. Insertion sort: move element i left past every larger element.
                                      Slide 23: Insertion sort inner loop
                                      Exam weight Low
                                        Slide 24: Insertion sort: Java implementation
                                        Exam weight Low
                                          Slide 25: Insertion sort: animation
                                          Exam weight Low
                                            Slide 26: Insertion sort: animation
                                            Exam weight Low
                                              Slide 27: Insertion sort: animation
                                              Exam weight Low
                                                Slide 28: Insertion sort: mathematical analysis
                                                Exam weight High
                                                1. Insertion sort: best case (sorted) ~n compares; worst (reverse) ~n²/2; average ~n²/4.
                                                🎯 How this can come up · 1 question
                                                MCQ

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

                                                Insertion sort: trace

                                                29
                                                Exam weight Low
                                                  Slide 30: Insertion sort: analysis
                                                  Exam weight Low
                                                    Slide 31: 9 casserarue
                                                    Exam weight Low

                                                      Insertion sort: practical improvements

                                                      Half exchanges. Shift items over (instead of exchanging).

                                                      Eliminates unnecessary data movement.

                                                      ・ ・

                                                      No longer uses only less

                                                      and exch

                                                      to access data.

                                                      A C H H I M N N P Q X Y K B I N A R Y

                                                      Binary insertion sort. Use binary search to find insertion point.

                                                      N N

                                                      Number of compares ~ lg.

                                                      ・ ・

                                                      But still a quadratic number of array accesses.

                                                      A C H H I M N N P Q X Y K B I N A R Y

                                                      binary search for first key > K

                                                      32
                                                      Exam weight Low