Programming Langauge : C++ Write a linked list bubble sort program, which sorts
ID: 3828439 • Letter: P
Question
Programming Langauge : C++
Write a linked list bubble sort program, which sorts unsorted file names in a listbox.
Using the Code provided, everything else is working, just need the bubble sort to work. I think i messed up on some of these. The program needs to count, comparison, looping, optimization and swap. I included my header files below.
I have open file, filling list box, etc working, just need the file to sort the following unsorted names in the listbox. I bolded which code inserts back into list box. That might need changes also.
NOONAN, TED
ROMANO, BRYAN
REITZ, LIZZIE
AHERN, GROVER
GEYER, KITTY
CROCKER, MONTY
CHADWICK, SHELLEY
COWART, SPARKLE
WREN, BRANDA
CURIEL, LEANN
CHAO, MEAGHAN
ELKINS, MERLE
int BubbleSort()
{
int iCompareCount = 0;
NodeClass* tempNode = new NodeClass;
string strData1;
string strData2;
int iNodeCount = 0;
bool isSorted;
list->SetCurrentNode(list->GetFirstNode());
list->Next();
while (list->GetCurrentNode() != nullptr)
{
iNodeCount++;
list->Next();
}
list->SetCurrentNode(list->GetFirstNode());
for (int i = 1; i < iNodeCount; i++)
{
tempNode = list->GetCurrentNode();
strData1 = list->GetCurrentNode()->GetString();
strData2 = list->GetCurrentNode()->GetNextNode()->GetString();
isSorted = false;
for (int j = 0; j < iNodeCount - i; j++)
{
iCompareCount++;
NodeClass * temp1 = list->GetCurrentNode();
NodeClass * temp2 = list->GetCurrentNode()->GetNextNode();
if (temp1->GetString() > temp1->GetString())
{
tempNode = temp1;
temp2->SetPrevNode(temp1->GetPrevNode());
tempNode->SetPrevNode(temp2);
tempNode->SetNextNode(temp2->GetNextNode());
temp2->SetNextNode(tempNode);
list->SetCurrentNode(temp1);
}
if (isSorted)
{
list->Insert(strData2);
list->SetCurrentNode(tempNode);
list->Delete();
tempNode = list->GetCurrentNode();
break;
}
}
}
return iCompareCount;
}
----------------------------------------------------------------------------------------------------------------------
LinkedListClass.h
#pragma once
class LinkedListClass
{
public:
LinkedListClass();
~LinkedListClass();
void Append(string);
void Insert(string);
void Delete();
void Next();
void Previous();
NodeClass* GetFirstNode();
NodeClass* GetLastNode();
NodeClass* GetCurrentNode();
void SetCurrentNode(NodeClass*);
private:
NodeClass* firstNode;
NodeClass* lastNode;
NodeClass* currentNode;
};
NodeClass.h
class NodeClass
{
public:
NodeClass();
~NodeClass();
void SetString(string); // sets strString
string GetString(); // returns strString
void SetNextNode(NodeClass*); // sets pointer to next node
void SetPrevNode(NodeClass*); // sets pointer to previous node
NodeClass* GetNextNode(); // returns pointer to next node
NodeClass* GetPrevNode(); // returns pointer to previous node
private:
string strText; // string from file
NodeClass* nextNode; // pointer to next node
NodeClass* prevNode; // pointer to [revopios node
};
Explanation / Answer
//Modified bubblesort function
int BubbleSort()
{
int iCompareCount = 0; // total # of comparisons
NodeClass* tempNode = new NodeClass; // hold item to be compared
string strData; // hold string to be compared
int iNodeCount = 0; // length of linked list
bool isSorted = false; // if a move needs to happen
// count number of nodes
list->SetCurrentNode(list->GetFirstNode()); // start at top
list->Next(); // start with the 2nd node
while (list->GetCurrentNode() != nullptr) // run through list
{
iNodeCount++; // count
list->Next(); // move
}
list->SetCurrentNode(list->GetFirstNode()); //Reset pointer to first node in list for sorting
for (int iteration = 1; iteration < iNodeCount; iteration++)
{
for (int index = 0; index < iNodeCount - iteration; index++)
{
iCompareCount++;
NodeClass * t1=list->GetCurrentNode();
NodeClass * t2=list->GetCurrentNode()->GetNextNode();
if (t1->GetString() > t2->GetString()) // top of list
{
tempNode = t1;
t2->SetPrevNode(t1->GetPrevNode());
tempNode->SetPrevNode(t2);
tempNode->SetNextNode(t2->GetNextNode());
t2->SetNextNode(tempNode);
list->SetCurrentNode(t1);
}
}
}
return iCompareCount;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.