SORTING
and Searching
Insertion Sort
If you were any good at The Sorting Game, odds are you were using one
of two strategies. The first of these is called repeated
insertion. In repeated insertion, you try and grow a longer
and longer list of sorted elements. Every time you pick up a new
element, you find it's position in the sorted list you already have
and insert it there.
This is how the Insertion Sort algorithm works. The front
part of the list is kept in sorted order, and elements are taken from
the back part of the list and inserted into the front. Every time a
new element is inserted into the sorted list, it's length increases
until eventually the entire list is sorted.
|
|
Now let's look at another possible strategy.
[Selectin' Things]