CS210 · Annotated SlidesSorting — Quick Sort
Sorting · Annotated slides

Quick Sort

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

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: Two classic sorting algorithms: mergesort and quicksort
    Exam weight Low

      Quicksort t-shirt

      3
      Exam weight Low
        Slide 4: Slide 4
        Exam weight Low
          Slide 5: ocntime
          Exam weight Low
            Slide 6: join
            Exam weight Low
              Slide 7: 3 7 2 4 1 5 9
              Exam weight Low
                Slide 8: Tony Hoare
                Exam weight Low

                  Tony Hoare

                  ・

                  Invented quicksort to translate Russian into English.

                  ・ [ but couldn't explain his algorithm or implement it! ] ・

                  Learned Algol 60 (and recursion).

                  Implemented quicksort.

                  ・

                  Tony Hoare

                  1980 Turing Award

                  “ There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deÞciencies, and the other way is to make it so complicated that there are no obvious deÞciencies. The Þrst method is far more difÞcult. ” “ I call it my billion-dollar mistake. It was the invention of the null reference in 1965… This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. ”

                  Tony Hoare
                  9
                  Exam weight Low
                    Slide 10: Bob Sedgewick
                    Exam weight Low
                      Slide 12: ABCDEFGHijklmnoparstuvwxyz.pivf.iq too
                      Exam weight Low
                        Slide 13: Quicksort partitioning demo
                        Exam weight Low
                          Slide 14: Quicksort: Java code for partitioning
                          Exam weight Low
                            Slide 15: Quicksort: Java implementation
                            Exam weight Low
                            1. Shuffle first, partition, then sort each part recursively.
                            Slide 16: Quicksort trace
                            Exam weight Low
                              Slide 17: Quicksort animation
                              Exam weight Low
                                Slide 18: Quicksort: implementation details
                                Exam weight Low
                                  Slide 19: Quicksort: empirical analysis (1961)
                                  Exam weight Low
                                    Slide 20: Quicksort: empirical analysis
                                    Exam weight Low
                                      ★ Past exam
                                      Slide 21: perfectly geg
                                      Exam weight High
                                      1. Best case: ~N lg N compares. Worst case (already sorted, no shuffle): ~N²/2.

                                      Asked in a real exam

                                      ★ Quiz 2 question bank · which sequence makes quicksort O(n²)
                                      🎯 How this can come up · 1 question
                                      MCQ

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

                                      Slide 22: sorted
                                      Exam weight Low
                                        Slide 23: Quicksort: average-case analysis
                                        Exam weight Low
                                          Slide 24: Quicksort: average-case analysis
                                          Exam weight Low
                                            Slide 25: Quicksort: average-case analysis
                                            Exam weight Low
                                              Slide 26: Quicksort: average-case analysis
                                              Exam weight Low
                                                Slide 27: Quicksort: average-case analysis
                                                Exam weight Low
                                                  Slide 28: Quicksort: summary of performance characteristics
                                                  Exam weight High
                                                  1. Average ~1.39 N lg N compares; in place; not stable.
                                                  🎯 How this can come up · 1 question
                                                  MCQ

                                                  Quicksort’s average running time is:

                                                  Slide 29: Quicksort properties
                                                  Exam weight Low
                                                    Slide 30: Slide 30
                                                    Exam weight Low
                                                      Slide 31: Duplicate keys
                                                      Exam weight Low
                                                        Slide 32: Duplicate keys
                                                        Exam weight Low
                                                          Slide 33: What is the result of partitioning the following array?
                                                          Exam weight Low
                                                            Slide 34: Partitioning an array with all equal keys
                                                            Exam weight Low
                                                              Slide 35: Duplicate keys: the problem
                                                              Exam weight Low
                                                                Slide 36: Sorting summary
                                                                Exam weight Low
                                                                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).

                                                                System sort in Java 7

                                                                Arrays.sort

                                                                .

                                                                Has method for objects that are Comparable

                                                                .

                                                                ・ ・

                                                                Has overloaded method for each primitive type.

                                                                Has overloaded method for use with a Comparator

                                                                .

                                                                ・ ・

                                                                Has overloaded methods for sorting subarrays.

                                                                Algorithms.

                                                                ・

                                                                Dual-pivot quicksort for primitive types.

                                                                Timsort for reference types.

                                                                ・ Q. Why use different algorithms for primitive and reference types?

                                                                System sort in Java 7
                                                                37
                                                                Exam weight Low
                                                                  Slide 38: Slide 38
                                                                  Exam weight Low
                                                                    Slide 39: swap
                                                                    Exam weight Low