This is just about the implementation of insertion sort. Topics such as the efficiency, the precise analysis of the algorithm itself are not covered here (since i'm not good at these :).
Below is the C-like pseudo code and we don't care how to insert the element into the sorted array now:
Start from 2nd elements because aArray[0] is sorted.
For (each element in the unsorted array)
Insert aArray[i] (i starts from 1) to aArray[0..i-1] which is sorted;
|
The translation to C code is quite straight-forward:
void InsertionSort(int* aArray, int aNElems)
{
if (aArray == NULL) return;
for (int i = 1; i < aNElems; ++i)
{
Insert(aArray, i, aArray[i]);
}
return;
}
|
Now we need to know how to insert the element to the sorted array. Below is the C-like pseudo code:
For (each element in the sorted array (backward))
if (key < current element)
move current element forward;
else
break;
Insert the key to the found location;
|
Still, the translation to C code is straight-forward:
void Insert(int* aArray, int aLoopInvariantLen, int aKey)
{
int i = aLoopInvariantLen;
for (; i > 0; --i)
{
// Move the bigger one to next
if (aKey < aArray[i - 1])
{
aArray[i] = aArray[i - 1];
}
else
{
break;
}
}
// The location of aKey in aArray is found, insert aKey.
aArray[i] = aKey;
return;
}
|
阅读(1323) | 评论(3) | 转发(0) |