Double linked list Insert Sort Error
I have implemented an insert sort on a double link list (highest to lowest) from a 10,000 ints file and outputs the file in reverse order.
As far as I know, I have implemented such a program, however, I noticed that in the output file one number is out of place. Every other number is in the correct order.
The number is out of place - it is a duplicate number, but other occurrences of that number are in the correct order. It's just weird how this number is misplaced. In addition, the unsorted number is only 6 unsynchronized locations.
I have been reviewing my program for several days now, I donโt know where the problem is, so I am asking you for help.
Below is the code,
(side of note: can my question be deleted by itself? Rather, my colleges are not eating 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);
}
}
Thank you for your time.
a source to share
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 is inserted at the end instead of โ back. By the way, you insert equal integers in reverse order, they are read. For integers it doesn't matter, but it might be if you've inserted other objects. I would change the code of the insert method:
node* temp;
temp = this->front;
while(temp!=NULL)
{
if(temp->value > inValue)
{
insertBefore(inValue, temp);
return;
}
temp = temp->next;
}
insertBack(inValue);
a source to share
Just a few comments.
while(!in.eof())
This will not stop the inner loop from showing an EOF error. Do you want to
while ( in >> readInt )
Besides,
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 the loop termination condition.
My guess is that some inconsistency between multiple binding conventions is causing the erroneous value to end up in the middle of the list.
a source to share