Insertion Sort & Selection Sort

Elementary Sorts

Rules of the Game

• Sorting Problem: Rearrange an array of $n$ items into ascending order by key.
  • Item: The data being sorted (e.g., student record).
  • Key: The part of the item used for sorting (e.g., name, ID).
• Example: Sorting student records in a university system by name, ID, etc.

Sorting Applications

• Alphabetical order (e.g., contacts in a phone).
• Numerical order (e.g., Library of Congress numbers).
• Chronological order (e.g., FedEx packages).
• Other examples include sorting playing cards, contacts, and Hogwarts houses, and search engine results.

Goal: Sort Any Type of Data

• Total Order: A binary relation $≤$ that satisfies:
  • Antisymmetry: If both $v ≤ w$ and $w ≤ v$, then $v = w$.
  • Transitivity: If both $v ≤ w$ and $w ≤ x$, then $v ≤ x$.
  • Totality: Either $v ≤ w$ or $w ≤ v$ or both.
• Examples of Total Order: Numerical, chronological, and lexicographic orders.
• Non-Examples of Total Order:
  • Ro-sham-bo (violates transitivity).
  • Course prerequisites (violates totality).
  • Predator-prey (violates antisymmetry).

Callbacks

• Goal: Sort data of types like String, Double, and java.io.File without hardwiring type-specific information.
• Callback: A reference to executable code.
  • Client passes an array of objects to a $sort()$ function.
  • The $sort()$ method calls the object’s $compareTo()$ function as needed.
• Implementing Callbacks:
  • Java: Interfaces.
  • C: Function pointers.
  • C++: Class-type functors.
  • C#: Delegates.
  • Python, Perl, ML, Javascript: First-class functions.

Callbacks: Java Interfaces

• Interface: A type that defines a set of methods that a class can provide.
• Class Implementing Interface: Must implement all interface methods.
• Impact:
  • Any String object can be treated as an object of type Comparable.
  • On a Comparable object, you can invoke the $compareTo()$ method.
  • Enables callbacks.
• Example: Code snippet demonstrating the use of Comparable interface in Java to sort Strings

Java.lang.Comparable API

• Comparable Interface: Used to define a natural order for objects.
• $v.compareTo(w)$
  • Defines a total order.
  • Returns a negative integer if $v < w$, zero if $v = w$, and a positive integer if $v > w$.
  • Throws an exception if incompatible types (or either is null).
• Built-in Comparable Types: Integer, Double, String, Date, File, etc.
• User-Defined Comparable Types: Implement the Comparable interface.

Implementing the Comparable Interface

• Example using a simplified version of java.util.Date.

Selection Sort

• Algorithm: Scans from left to right.
• Invariants:
  • Entries to the left of $i$ (including $i$) are fixed and in ascending order.
  • No entry to the right of $i$ is smaller than any entry to the left of $i$.
• Finds the index $min$ of the smallest remaining entry in iteration $i$.
• Swaps $a[i]$ and $a[min]$.

Selection Sort Inner Loop

• Move the pointer $i$ to the right.
• Identify the index of the minimum entry on the right.
• Exchange $a[i]$ into position.

Helper Functions

• Less: Is item $v$ less than $w$? (Uses $compareTo$).
• Exchange: Swap item in array $a[]$ at index $i$ with the one at index $j$.

Selection Sort: Java Implementation

• Code snippet showing a Java implementation of the selection sort algorithm.

Selection Sort: Mathematical Analysis

• Proposition: Selection sort uses $(n - 1) + (n - 2) + … + 1 + 0 ~ n^2 / 2$ compares and $n$ exchanges to sort any array of $n$ items.
• Running Time: Insensitive to input (quadratic time, even if input is sorted).
• Data Movement: Minimal (linear number of exchanges—exactly $n$).

Insertion Sort

• Algorithm: Scans from left to right.
• Invariants:
  • Entries to the left of $i$ (including $i$) are in ascending order.
  • Entries to the right of $i$ have not yet been seen.
• In iteration $i$, swap $a[i]$ with each larger entry to its left.

Insertion Sort: Inner Loop

• Move the pointer $i$ to the right.
• Moving from right to left, exchange $a[i]$ with each larger entry to its left.

Insertion Sort: Java Implementation

• Code snippet showing a Java implementation of the insertion sort algorithm.

Insertion Sort: Mathematical Analysis

• Proposition: To sort a randomly ordered array with distinct keys, insertion sort uses ~ $¼ n^2$ compares and ~ $¼ n^2$ exchanges on average.

Insertion Sort: Analysis

• Worst Case: If the array is in descending order (and no duplicates), insertion sort makes ~ $½ n^2$ compares and ~ $½ n^2$ exchanges.
• Best Case: If the array is in ascending order, insertion sort makes $n – 1$ compares and $0$ exchanges.

Insertion Sort: Partially Sorted Arrays

• Def: An inversion is a pair of keys that are out of order.
• Def: A family of arrays is partially sorted if the number of inversions is $≤ c n$.
• Proposition: Insertion sort runs in linear time on partially sorted arrays.
• Pf: Number of exchanges in insertion sort = number of inversions.

Insertion Sort: Practical Improvements

• Half Exchanges: Shift items over (instead of exchanging) to eliminate unnecessary data movement.
• Binary Insertion Sort: Use binary search to find the insertion point. This reduces the number of compares to ~ $n lg n$, but still has a quadratic number of array accesses.

Shuffling

• Goal: Rearrange array so that the result is a uniformly random permutation.

Shuffle Sort

• Generate a random real number for each array entry.
• Sort the array.
• Proposition: Shuffle sort produces a uniformly random permutation.

War Story (Microsoft)

• Microsoft antitrust probe by EU: Microsoft agreed to provide a randomized ballot screen for users to select a browser.
• Microsoft's initial implementation in Javascript used a comparator that always returned a random answer, which failed to implement a total order.

Different Orderings

• Sorting music library by artist and song name are provided as examples.

Comparable Interface: Review Natural Order

• Code snippet showing a Java implementation of the Comparable interface for the Date object.

Comparator Interface

• Sort using an alternate order.
• Required property: Must be a total order.
• Examples: String order (natural, case-insensitive, Spanish), British phone book order.
• Bottom line: Decouples the definition of the data type from the definition of what it means to compare two objects of that type.

Comparator Interface: System Sort

• To use with Java system sort:
  • Create Comparator object.
  • Pass as the second argument to Arrays.sort().

Comparator Interface: Using with Our Sorting Libraries

• To support comparators in our sort implementations:
  • Pass Comparator to both sort() and less(), and use it in less().
  • Use Object instead of Comparable.

Comparator Interface: Implementing

• To implement a comparator:
  • Define a (nested) class that implements the Comparator interface.
  • Implement the compare() method.
  • Provide client access to Comparator.
• Example: Implementation of NameOrder and SectionOrder comparators for a Student class.
• Code example of the Student class

Stability

• A stable sort preserves the relative order of items with equal keys.

Stability: Insertion Sort

• Proposition: Insertion sort is stable.
• Pf: Equal items never move past each other.

Stability: Selection Sort

• Proposition: Selection sort is not stable.
• Pf: Long-distance exchange can move an equal item past another one.