Programming: Modify the source code for the insertion sort so that it can sort a
ID: 3836282 • Letter: P
Question
Programming: 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)?
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--){
if (key < num[i]) {
num[i + 1] = num[i]; // larger values move right
insertionNeeded = true;
}
else
break;
}
if (insertionNeeded)
num[i + 1] = key; //Put key into its proper location
}
}
Explanation / Answer
void insertion_sort(std::list <int> &num)
{
int i, j, key;
bool insertionNeeded = false;
list<int> temp;
temp.push_front(num.front());
num.pop_front();
while(num.size()) {
key = num.front();
if (key < temp.front()) {
temp.push_front(num.front());
}
else if (key > temp.back()) {
temp.push_back(key);
}
else
{
int sz = temp.size();
int i=0;
for (; i < sz; i++)
{
if ( key < temp.front())
{
temp.push_back(key);
break;
}
//rotate
temp.push_back(temp.front());
temp.pop_front();
}
while (i++ < sz)
{
temp.push_back(temp.front());
temp.pop_front();
}
}
num.pop_front();
}
num = temp;
}
Yes, there is difference in performance.
Vectors are array implementation wich makes them efficient for accessing elements directly without having to iterate the whole array. But they are inefficient in shifting.
Lists are linkedList implementation, so efficient in shifting elements but for accessing a middle item, it becomes costly.
InsertionSort is preferable for arrays that are almost sorted
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.