9. Sorting and Search

9.1 Soring: Introduction

NOTE: Java’s compareTo() compares strings character by character; the first difference determines order, or the shorter string comes first if one is a prefix.

9.2 Selection sort

The outer loop iterates $i$ from $0$ to $N-1$

9.3 Insertion sort

The outer loop iterates $i$ from $1$ to $N$

For sorted or nearly sorted inputs: $O(N)$
Nearly sortd: a few elements not in sorted order

9.4 Bubble sort (optional)

9.5 Merge sort

9.6 Quicksort

$h$ the index of the last element in the low parition
Two equal-sized parts will have $logN$ levels and $NlogN$ comparisons
Smallest or largest pivot will have $N-1$ levels and $N(N-1)$ comparisons

NOTE: this motherfucker zyBook executes h-- after swapping and then fucking returns h as the last index of the LOW partition

9.7 Heapsort

Heapify: turn an array into a heap

Starts on internal node with largest index continues down to root node
Largest internal node: $\lfloor \frac{N}{2}\rfloor -1$

NOTE: heapify traverses bottom-up but fucking percolates down

Heapsort has two phases.

1. Heapify: traverse bottom-up and percolate down to build a max-heap
2. Sorting: swap root with end, shrink the heap, percolate down, and repeat

9.8 Bucket sort