The Doubly Linked List Class In this assignment, you are to implement a primitiv

Question

The Doubly Linked List Class In this assignment, you are to implement a primitive sort. You arc required to use the doubly linked list discussed in class. The code is the file list-class. cxx (available on the announcement page) and should be copied into your main program. List Sort Now implement the list sort described below: Initialization The user inputs n. Then n random numbers between I and 10000 are are inserted into a linked list. Loop Write the numbers in sorted order to the screen. In order to do this you repeatedly find the minimum, write it to the screen and delete it until the list is empty. Run Time Experiments Tabulate the user run time for n = 10000, 20000, 30000, 40000, 50000. The command is time./a.out >/dev/null Explanation: In order to measure run time the output must be redirected the to/dev/null (or else your screen will fill up with thousands of numbers.) To measure user run time you use the command time command, which is described in greater detail on the announcement page.

Explanation / Answer

#include "list_class.cpp"
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

List::iterator findMin(List lst){
   List::iterator itr, minItr = lst.begin();
   for(itr = lst.begin(); itr != lst.end(); itr++){
       if(*itr < *minItr){
           minItr = itr;
       }
   }
   return minItr;
}

int main(){
   srand(time(NULL));
   int n;
   cout << "Enter n: ";
   cin >> n;
   List lst;
   for(int i = 0; i < n; ++i){
       int val = (rand() % 10000) + 1;
       lst.push_back(val);
       cout << val << endl;
   }
   cout << endl;
   while(!lst.empty()){
       List::iterator itr = findMin(lst);
       cout << *itr << ", ";
       lst.erase(itr);
   }
   cout << endl;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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