Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1714448
  • 博文数量: 177
  • 博客积分: 9416
  • 博客等级: 中将
  • 技术积分: 2513
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-06 16:08
文章分类

全部博文(177)

文章存档

2013年(4)

2012年(13)

2011年(9)

2010年(71)

2009年(12)

2008年(11)

2007年(32)

2006年(25)

分类: C/C++

2009-10-23 11:39:30

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;
}


阅读(1321) | 评论(3) | 转发(0) |
给主人留下些什么吧!~~

fera2009-11-16 13:54:15

Selection Sort: int FindPos(int* aArray, int aCurPos, int aLen) { int pos = aCurPos; int key = aArray[aCurPos]; // Start from current position which is the begin of unsorted array. for (int i = aCurPos; i < aLen; ++i) { if (aArray[i] < key) { // Update the position found and the smallest element. pos = i; key = aArray[i]; } } return pos; } void SelectionSort(int* aArray, int aLen) { /

fera2009-10-26 10:28:31

自娱自乐呢

chinaunix网友2009-10-26 10:25:33

proposal:用中文写博吧,用英文索引一些类似的技术不难,难得是有人翻译过来。就当多为自己的国家做点事情吧:-)