开发者

Is this an insertion sort? [closed]

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. Closed 11 years ago.

I am reading "Introduction to Algorithms" and read about the insertion sort.

I tried to implement it myself without first reading their solution.

Here is my solution, is this insertion sort?

#include <iostream>

using namespace std;

int main()
{
    // initialize an unsorted array
    int a[] = {5,6,4,7,3,8,2,9,0,1};

    // define variables
    int i,j,tmp;

    for (int j=1; j<10; ++j)
    {
        for (int i=0;i<j;++i)
        {
            if (a[j] < a[i])
            {
                tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
            }
        }

    }

    for (i=0;i<10;++i)
    {
        cout << a[i] << endl;
    }

    return 0;
}

Ok, I've read it, and understand why it wasn't insertion sort... this is much better.

   #include <iostream>

    using namespace std;

  开发者_JS百科  int main()
    {
        // initialize an unsorted array
        int a[] = {5,6,4,7,3,8,2,9,0,1};

        // define variables
        int i,j,key,c;

        for (int j=1; j<10; ++j)
        {
            key = a[j];
            i = j - 1;

            while(i>=0 && a[i] > key)
            {
                a[i+1] = a[i];
                i = i - 1;
            }
            a[i+1] 

= key;
        ++c;
    }

    for (i=0;i<10;++i)
    {
        cout << a[i] << endl;
    }

    cout << endl << c << endl;
    return 0;
}


Your solution seems to be bubble sort, not insertion sort.


It looks like insertion sort to me. You are creating sorted array (a[0...j]) one element at a time.

Your insertion is unusual and inefficient. To insert a[j] into a[0...j] you don't need to compare it to every element.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜