Insertion
Sort
(Up to Basic
Computer Science : Lists and Arrays
: Sorting Algorithms)
Insertion Sort, like Selection Sort,
is a fairly intuitive algorithm. Insertion Sort's advantages lie
in that it works really well with almost sorted arrays. In
the non-computer world, it is often used by card players sorting
cards that are dealt one at a time.
Imagine that you have the following 5 cards dealt to you in this
order (we only care about the numbers, so we'll ignore the suits): 3, 2, 4, 5, 1.
First, we're dealt the card with the 3
on it. Then, we're dealt the 2, which
is inserted before the 3. Then,
we're dealt the 4 and the 5,
both of which are put at the end. When we are given the 1,
it is inserted before the 2. Now, we've
been dealt five cards, and so the hand been sorted.
Of course, when we are sorting an array, we don't get the elements
one at a time. Instead, we get them all at once, but we can still visualize them as if we are being given them one at a time.
We just ignore the elements that haven't been "dealt"
to us yet.
Here's another example: let's sort this list: 3,
5, 7, 2, 8, 1, 9, 0, 4, 6.
The sort goes something like this:
| Round |
Numbers
"Dealt" |
Numbers
Not "Dealt" |
| 1 |
3 |
5 7 2 8 1 9 0 4 6 |
| 2 |
3 5 |
7 2 8 1 9 0 4 6 |
| 3 |
3 5 7 |
2 8 1 9 0 4 6 |
| 4 |
2 3 5 7 |
8 1 9 0 4 6 |
| 5 |
2 3 5 7 8 |
1 9 0 4 6 |
| 6 |
1 2 3 5 7 8 |
9 0 4 6 |
| 7 |
1 2 3 5 7 8 9 |
0 4 6 |
| 8 |
0 1 2 3 5 7 8 9 |
4 6 |
| 9 |
0 1 2 3 4 5 7 8 9 |
6 |
| 10 |
0 1 2 3 4 5 6 7 8 9 |
|
Notice that the numbers that have been "dealt" are always
in order..
Easy and simple, right? Well, the way the computer does Insertion
Sort isn't quite so simple.
The computer begins with the new card at the end and swaps it backwards
until it is in the correct location. So, the card with the 1 would
have to be swapped 4 times. This method becomes extremely long in
certain cases, such as when the list begins completely backwards
(5, 4, 3, 2, 1). That particular formation is the worst case
scenario, and for that, Insertion Sort is very, very slow.
So, a man by the name of Shell created a sorting algorithm called
the Diminishing-Increment Insertion Sort, also known simply
as Shell Sort. Mr. Shell tried to get the benefits of Insertion
Sort without the drawbacks. Unfortunately, Mr. Shell's Sort is far
from being the fastest algorithm, and it is more complex than Insertion
or Selection Sort.
Still, for most cases, Insertion Sort is much faster than Selection
Sort, and it is not very complicated to type, so it is used
often in various computer science projects.
There is a nicely commented, usable version of Insertion Sort that
you can download at our site:
Download from Source
Code Repository: sorts/insertion.h
Home 
