Modify the source code for the insertion sort so that it can sort a list of inte

Question

Modify the source code for the insertion sort so that it can sort a list of integers. Is there a difference in performance (compared to the vector-based one)?

#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>

using namespace std;

void insertion_sort(std::vector <int> &num) {
   int i, j, key;
   bool insertionNeeded = false;

   for (j = 1; j < num.size(); j++) {
       key = num[j];
       insertionNeeded = false;
       for (i = j - 1; i >= 0; i--) { // larger values move right

           if (key < num[i]) {
               num[i + 1] = num[i];
               insertionNeeded = true;
           }
           else
               break;
       }
       if (insertionNeeded)
           num[i + 1] = key; //Put key into its proper location
   }
}

Explanation / Answer

example output:

b) There is no speedup as such. But the linked list implementation takes the double amount of memory than vector one.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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