definitions

An ordering relation << for keys a, b, and c has the following properties:

  • Law of Trichotomy: Exactly one of a << b, a = b, b << a is true.
  • Law of Transitivity: If a << b, and b << c, then a << c.

Java: Comparable

In java, compare or compareTo methods are used.

1
2
3
4
5
6
7
import java.util.Comparator;
 
public class LengthComparator implements Comparator<String> {
    public int compare(String x, String b) {
        return x.length() - b.length();
    }
}

basic sorts

selection sort

  1. Find the smallest item.
  2. Swap that item to the front.
  3. Repeat until all items are fixed (there are no inversions).
    runs in Θ(N^2) time

heapsort

  1. insert all the items into a max heap and create and output array.
  2. Then, we repeatedly delete the largest item from the max heap and put the largest item at the end part of the output array.
    overall running time: Θ(𝑁log⁡𝑁)
  • Inserting N items into the heap: 𝑂(𝑁log⁡𝑁).
  • Selecting the largest item: Θ(1).
  • Removing the largest item: 𝑂(log⁡𝑁).

in-place heapsort

instead of constructing a totally new heap, exchange the array to make them in order of the heap.
we can use a process known as bottom-up heapification to convert the input array into a heap. Bottom-up heapification involves moving in reverse level order up the heap, sinking nodes to their appropriate location as you move up.

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

![[Pasted image 20240516104440.png]]

merge sort

  1. Split the items into half.
  2. Mergesort each half.
  3. Merge the two sorted halves to form the final result.

insertion sort

  1. divide the “sorted” part, and the “unsorted” part
  2. find a element in unsorted part, and then insert it into the sorted part.

quicksort

simple quicksort

The core idea behind Quicksort involves partitioning.
Partitioning on that pivot element (x) involves rearrange a[] such that:

  1. x moves to some position j (can be the original position of i)
  2. All array elements to the left of x are less than or equal to x (<= x)
  3. All array elements to the right of x are greater than or equal to x (>= x)
    then, call quicksort recursively, and the quicksort have been done.
    Coincidentally, quicksort is empirically the fastest sort for most common situations.

complexity

best: O(nlogn)
worst: O(n^2)

drawbacks

the choosing of the split point is more than important!

improvement

randomness

  • pick pivots randomly
  • shuffle items before sort

Smarter Pivot Selection

to choose a “good” pivot

  • constant time pivot pick: pick up a few items and then choose the “best” one among them
  • linear time pivot pick: always select the “median”