How would i change this insertion sort into a bubble sort? im confused about the
ID: 3828586 • Letter: H
Question
How would i change this insertion sort into a bubble sort? im confused about the concept of bubble sorts..
int iCompareCount = 0; // total # of comparisons
NodeClass* tempNode = new NodeClass; // hold item to be compared
string strData; // holds string to be compared
int iNodeCount = 0; // length of linked list
bool bMove; // if a move needs to happen
// count the number of nodes
list->SetCurrentNode(list->GetFirstNode()); // start at top
while (list->GetCurrentNode() != nullptr)
{
iNodeCount++; //count
list->Next(); // advance
}
list->SetCurrentNode(list->GetFirstNode()); // move to top of list
list->Next(); // start with the second node
for (int i = 1; i < iNodeCount; i++)
{
tempNode = list->GetCurrentNode(); // save address of current node
strData = list->GetCurrentNode()->GetString(); //get the node's data for comparison
bMove = false; // true if need to move node
// run backward till either a match or at top of list
do
{
iCompareCount++; //count cpmparison
if (list->GetCurrentNode() == list->GetFirstNode()) // top of list
bMove = true; // special treatment for top of list
else if (strData.compare( // if temp < prev
list->GetCurrentNode()->GetPrevNode()->GetString()) == 1)
bMove = true; // then move the temp node
if (bMove) // yes, move the temp node
{
list->Insert(strData); // insert this node
list->SetCurrentNode(tempNode); // reset location
list->Delete(); // delete the node we just moved
tempNode = list->GetCurrentNode(); // re-save temp location
break; // done with this loop
}
list->Previous(); // back up and try again
} while (list->GetCurrentNode() != nullptr); // loop till at top of list
} // for i
return iCompareCount;
Explanation / Answer
Bubble sort in C++ language:
void BubbleSort(apvector <int> &num)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = num.length( );
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] > num[j]) // ascending order simply changes to <
{
temp = num[j]; // swap elements
num[j] = num[j+1];
num[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.