Insertion Sort Problems

Question

I'm doing an insertion sort for my introductory C++ class, and it seems to be working, but I keep getting repeats in my sorted list.

In main

Storage s;
for (int i = 0; i < 20000; ++i)
{
    cout << "adding " << iss[i] << " to sorted list" << endl;
    s.Add(iss[i]);
}

and in Storage.cpp

    void Storage::Add(int num)
{
    it = mylist.begin();
    if (mylist.empty())
    {
        Node tem(num);
        mylist.push_front(tem);
    }
    else 
    {
        while (it != mylist.end())
        {
            if (num < (*it).GetNumber())
            {
                Node temp(num);
                mylist.insert(it, temp);
            }
            it++;
            if (it == mylist.end())
            {
                Node te(num);
                mylist.push_back(te);
            }
        }
    }
    it = mylist.begin();
    while (it != mylist.end())
    {
        cout << (*it).GetNumber() << ',';
        it++;
    }
    cout << endl << mylist.size() <<endl;
}

Node just stores the number that is being added to the list as well as the time, which is calculated inside Node.

I can't figure out why I'm getting repeats, thanks in advance for the help.

Have you tried debugging? Try stepping through the code and watch what happens. — crashmstr
– crashmstr, Commented Feb 6, 2014 at 19:48

m24p · Accepted Answer · 2014-02-06 19:52:56Z

1

Look at your while loop.

    while (it != mylist.end())  // Here
    {
        if (num < (*it).GetNumber()) // Here
        {
            Node temp(num);
            mylist.insert(it, temp); // and here
        }
        it++;
        if (it == mylist.end())
        {
            Node te(num);
            mylist.push_back(te); // And here
        }

Have you learned about break yet? You keep going through the loop after you add it, and add it at the end, too.

answered Feb 6, 2014 at 19:52

m24p

6744 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3280133 Over a year ago

Just saw that myself, been looking at that same code all day, can't believe I missed that!

m24p Over a year ago

@Wajahat Yes you did, at the same time I was composing an answer that said it more clearly. It would be nice if one of our answers gets accepted, wouldn't it? And maybe both get upvoted?

Wajahat · Accepted Answer · 2014-02-06 19:50:40Z

1

In second if condition of your while loop, you always add a new node at the end of the list that is causing repeats.

answered Feb 6, 2014 at 19:50

Wajahat

1,6434 gold badges21 silver badges49 bronze badges

Comments

Vlad from Moscow · Accepted Answer · 2014-02-06 19:58:15Z

0

I think that the problem is in this loop

    while (it != mylist.end())
    {
        if (num < (*it).GetNumber())
        {
            Node temp(num);
            mylist.insert(it, temp);
        }
        it++;
        if (it == mylist.end())
        {
            Node te(num);
            mylist.push_back(te);
        }
    }

If the list has one element then after it++ the iterator will be equal to end() and you will add a new element. After that the current iterator end becames invalid. I would rewrite it the following way

    while ( it != mylist.end() && !( num < (*it).GetNumber() ) ) it++;
    Node temp( num );
    if (it == mylist.end()) mylist.push_back(temp);
    else mylist.insert(it, temp);

answered Feb 6, 2014 at 19:58

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Collectives™ on Stack Overflow

Insertion Sort Problems

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related