 |
The insertion sort, unlike the other sorts,
passes through the array only once.
The insertion sort is commonly compared to organizing a handful of
playing cards.
You pick up the random cards one at a time. As you pick up each card,
you insert it into
its correct position in your hand of organized cards.
The insertion sort splits an
array into two sub-arrays. The first sub-array (such as the cards in
your hand) is sorted and increases in size as the sort
continues. The second
sub-array (such as the cards to be picked up) is unsorted, contains all the elements
to yet be inserted into the first
sub-array, and decreases in size as the sort continues.
Let's look at our same example using the insertion sort for descending order.
|
|
Array at beginning: |
84 |
69 |
76 |
86 |
94 |
91 |
|
|
84 |
69 |
76 |
86 |
94 |
91 |
|
|
84 |
69 |
76 |
86 |
94 |
91 |
| |
84 |
76 |
69 |
86 |
94 |
91 |
| |
86 |
84 |
76 |
69 |
94 |
91 |
| |
94 |
86 |
84 |
76 |
69 |
91 |
|
2nd sub-array empty |
94 |
91 |
86 |
84 |
76 |
69 |
The insertion sort maintains the two
sub-arrays within the same array. At the beginning of the sort, the first
element in the first sub-array is considered
the "sorted array". With each pass through the loop, the
next element in the unsorted second sub-array is placed into its proper position in the
first sorted sub-array.
The insertion sort can be very fast and efficient when used with smaller
arrays. Unfortunately, it loses this efficiency when dealing with
large amounts of data.
// Insertion Sort Function for Descending Order
void InsertionSort( apvector <int> &num)
{
int i, j, key, numLength = num.length( );
for(j = 1; j < numLength; j++)
// Start with 1 (not 0)
{
key = num[j];
for(i = j - 1; (i >= 0) && (num[i] < key); i--)
// Smaller values move up
{
num[i+1] = num[i];
}
num[i+1] = key;
//Put key into its proper location
}
return;
}
|
