Given the declarations typedef int ComponentType; struct NodeType; typedef NodeT

Question

Given the declarations typedef int ComponentType; struct NodeType; typedef NodeType* NodePtr; struct NodeType { ComponentType component; NodePtr link; }; NodePtr lastPtr; NodePtr listPtr; NodePtr currPtr; NodePtr newNodePtr; write a void function that sorts the elements of the list in ascending order. The sort algorithm will scan the list, keeping a pointer to the lowest value seen thus far. When the end of the list is reached, the lowest value will be removed from that point and inserted at the end of a new list. After all of the elements have been moved from the original list to the new sorted list, change listPtr and currPtr to point to the first element of the new list. That way, when the function returns, the client code will simply see the list as having been sorted. Thank you!

Explanation / Answer

Code is as follows :

#include <iostream>
using namespace std;
typedef int ComponentType;
struct NodeType;
typedef NodeType* NodePtr;

struct NodeType{
ComponentType component;
NodePtr link;
};

NodePtr lastPtr;
NodePtr listPtr;
NodePtr currPtr;
NodePtr newNodePtr;

void sort(){
NodePtr sortedList = new NodeType;
NodePtr thisPtr = sortedList;
NodePtr smallest;
NodePtr tempPtr;
NodePtr prevPtr;
NodePtr smallPtr;
currPtr = listPtr;

while(currPtr != NULL){
tempPtr = listPtr;
smallest = tempPtr;
smallPtr = NULL;
prevPtr = NULL;

while(tempPtr != NULL){
if(tempPtr->component < smallest->component)
{
smallest = tempPtr;
smallPtr = prevPtr;
}

prevPtr = tempPtr;
tempPtr = tempPtr->link;
}

if(sortedList == NULL){
sortedList = smallest;
thisPtr = sortedList;
}
else
{
thisPtr->link = smallest;
thisPtr = thisPtr->link;
}

if(smallPtr == NULL)
{
smallPtr = smallest->link;
listPtr = smallPtr;
lastPtr = smallest;
currPtr = currPtr->link;
}
else
{
smallPtr->link = smallest->link;
lastPtr = smallest->link;
}
}

listPtr = sortedList->link;
}

int main(){
int n;
cout << "Enter how many number you want to sort :";
cin >> n;
cout << "Enter " << n << " Numbers : " << endl;

newNodePtr = new NodeType;
cin >> newNodePtr->component;

listPtr = newNodePtr;
lastPtr = newNodePtr;

currPtr = listPtr;
for(int node = 2; node <= n; node++){
newNodePtr = new NodeType;
cin >> newNodePtr->component;
currPtr->link = newNodePtr;
currPtr = newNodePtr;
}

currPtr->link = NULL;
lastPtr = currPtr;

sort();

cout << endl << "After Sorting List of Elements : ";
currPtr = listPtr;
while(currPtr != lastPtr->link){
cout << currPtr->component << " ";
currPtr = currPtr->link;
}

return 0;
}



Thank You.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.