Sorting

Question 1

Total order

Answer 1

A binary relation ≤ that satisfies:
- Antisymmetry: if v ≤ w and w ≤ v, then v=w.
- Transitivity: if v ≤ w and w ≤ x, then v ≤ x.
- Totality: either v ≤ w or w ≤ v or both

Question 2

Selection sort

Answer 2

• In iteration i, find index min of smallest remaining entry.
• Swap a[i] and a[min].

Question 3

Insertion sort

Answer 3

In iteration i, swap a[i] with each larger entry to its left.

Question 4

Analysis: Selection sort

Answer 4

Selection sort uses
(N - 1) + (N - 2) + ... + 1 + 0 ~ N²/2 compares and N exchanges.

Running time is insensitive to input. Quadratic time, even if input is sorted.
Data movement is minimal.

Question 5

Insertion sort: Best & worst case

Answer 5

If the array is in ascending order, insertion sort makes N-1 compares and 0 exchanges.

If the array is in descending order (and no duplicates), insertion sort makes ~ ½ N ² compares and ~ ½ N ² exchanges.

Question 6

Knuth shuffle

Answer 6

In iteration i, pick integer r between 0 and i uniformly at random.

Swap a[i] and a[r].

Question 7

Convex hull

Answer 7

The convex hull of a set of N points is the smallest perimeter fence enclosing the points.

Question 8

Basic plan

Mergesort

Answer 8

• Divide array into two halves
• Recursively sort each half
• Merge the two halves