Double Linked List Insertion Sorting Bug

Question

Hello,

I have implemented an insertion sort in a double link list (highest to lowest) from a file of 10,000 ints, and output to file in reverse order.

To my knowledge I have implemented such a program, however I noticed in the ouput file, a single number is out of place. Every other number is in correct order.

The number out of place is a repeated number, but the other repeats of this number are in correct order. Its just strange how this number is incorrectly placed. Also the unsorted number is only 6 places out of sync.

I have looked through my program for days now with no idea where the problem lies, so I turn to you for help.

Below is the code in question,

(side note: can my question be deleted by myself? rather my colleges dont thieve my code, if not how can it be deleted?)

    void DLLIntStorage::insertBefore(int inValue, node *nodeB)
{
    node *newNode;
    newNode = new node();
    newNode->prev = nodeB->prev;
    newNode->next = nodeB;
    newNode->value = inValue;

    if(nodeB->prev==NULL)
    {
        this->front = newNode;
    }
    else
    {
        nodeB->prev->next = newNode;
    }
    nodeB->prev = newNode;
}
void DLLIntStorage::insertAfter(int inValue, node *nodeB)
{
    node *newNode;
    newNode = new node();
    newNode->next = nodeB->next;
    newNode->prev = nodeB;
    newNode->value = inValue;

    if(nodeB->next == NULL)
    {
        this->back = newNode;
    }
    else
    {
        nodeB->next->prev = newNode;
    }   
    nodeB->next = newNode;
}
void DLLIntStorage::insertFront(int inValue)
{   
    node *newNode;
    if(this->front == NULL)
    {
        newNode = new node();
        this->front = newNode;
        this->back = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->value = inValue;
    }
    else
    {
        insertBefore(inValue, this->front);
    }

}   
void DLLIntStorage::insertBack(int inValue)
{   
    if(this->back == NULL)
    {
        insertFront(inValue);
    }
    else
    {
        insertAfter(inValue, this->back);
    }
}

ifstream& operator>> (ifstream &in, DLLIntStorage &obj)
{   
    int readInt, counter = 0;               

    while(!in.eof())
    {
        if(counter==dataLength) //stops at 10,000
        {
            break;
        }   

        in >> readInt;

        if(obj.front != NULL )
        {   
            obj.insertion(readInt);         
        }
        else
        {
            obj.insertBack(readInt);
        }
        counter++;
    }       
    return in;
}
void DLLIntStorage::insertion(int inValue)
{
    node* temp;
    temp = this->front;

    if(temp->value >= inValue)
    {
        insertFront(inValue);
        return;
    }
    else
    {       
        while(temp->next!=NULL && temp!=this->back)
        {
            if(temp->value >= inValue)
            {
                insertBefore(inValue, temp);
                return;
            }
            temp = temp->next;
        }
    }

    if(temp == this->back)
    {
        insertBack(inValue);
    }
}

Thankyou for your time.

Answer 1

Just some remarks.

while(!in.eof())

This will not stop the inside of the loop from seeing an EOF error. You want

while ( in >> readInt )

---

Also,

if(this->front == NULL)

and

void DLLIntStorage::insertion(int inValue)
{
    node* temp;
    temp = this->front;

    if(temp->value >= inValue)

do not mix. Either the front can be NULL, or it cannot. Likewise, you need to decide whether to use temp->next!=NULL or temp!=this->back, but not both, as a loop termination condition.

---

My guess would be that some inconsistency between multiple linking conventions is causing the errant value to get pushed into the middle of the list.

Answer 2

bit late for thieving lol :P

Answer 3

I don't like this part

else
{       
    while(temp->next!=NULL && temp!=this->back)
    {
        if(temp->value >= inValue)
        {
            insertBefore(inValue, temp);
            return;
        }
        temp = temp->next;
    }
}

if(temp == this->back)
{
    insertBack(inValue);
}

Imagine what happens if inValue is greater than all values except this->back->value. It gets inserted at the end instead before this->back. By the way, You are inserting equal integers in the reversed order, they are read. For integers it doesn't matter that much, but it could if You inserted other objects. I would change the code of the insertion method to this:

node* temp;
temp = this->front;
while(temp!=NULL)
{
    if(temp->value > inValue)
    {
        insertBefore(inValue, temp);
        return;
    }
    temp = temp->next;
}
insertBack(inValue);