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…(생략)
e number of items are out of
order, insertion_sort is O(n) . In this case, it does less opera-
tions than any other sorting algorithm.
For large datasets which aren’t nearly sorted, O(n 2 ) algo-
rithms are too slow (see tbl. 3.2). In these cases, we need more
efficient algorithms. The most famous efficient sorting algorithms
are Merge Sort (sec. 3.6) and Quicksort , both O(n log n) . Here’s
how Quicksort sorts a pile of cards:
1. If the pile has fewer than four cards, put them in the right
order and you’re done. Else, continue to step 2.
2. Choose at random any card from the pile to be the pivot .
3. Cards larger than the pivot go to a new pile to the right ; cards
smaller than the pivot go to a new pile to the left .
4. Start this procedure for each of the two piles you just created.
5. Join the left pile, pivot and right pile to get a sorted pile.
Algorithms | ??