Table of Contents
Chapter 1. Basics
Chapter 2. Complexity
Chapter 3. Strategy
Chapter 4. Data
Chapter 5. Algorithms
Chapter 6. Database
Chapter 7. Computers
Chapter 8. Programming
Prior to computers, sorting data was a major bottleneck that took
huge amounts of time to perform manually. When the Tabulating
ations in the 1890s, they sped up the US Census data compilation
by several years.
Many sorting algorithms exist. The simpler ones are O(n 2 ) .
Selection Sort (sec. 2.1) is one such algorithm. It’s the algorithm
people tend to use for sorting a physical deck of cards. Selection
Sort belongs to a big group of quadratic cost algorithms. We typi-
cally use them to sort small datasets of less than a thousand items.
One notable quadratic sorting algorithm is Insertion Sort . It’s very
efficient at sorting nearly sorted datasets, even if they are huge:
for i ← ? … list.length
j ← i
while j and list[j-?] ] list[j]
j ← j - ?
Run this algorithm in pen and paper, using a nearly sorted list of
numbers. For inputs where a negligibl…(생략)