AI Horizon: Intelligence and Reason in Computers
Introduction Home Essays Resources Contact Info
Essays
  Basic CS
General AI
Chess AI
Go AI

Resources
  Source Code
AI Tips and Tricks
Books
Links

Other
  Code Journal
Site Updates

An Affiliate of Cprogramming.com
 

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

All content is written and published by the people at or affiliated with AI Horizon <http://www.aihorizon.com/>.
Send any comments and suggestions to [email protected].

Please report any errors to [email protected].