Rewrite (IN C++) the Insertion sort function in chapter 11 AS A TEMPLATE FUNCTIO

Question

Rewrite (IN C++) the Insertion sort function in chapter 11 AS A TEMPLATE FUNCTION. Write a main function to test this function on integer, double and string type vectors.

#include

#include "util.h"

/**
Merges two adjacent ranges in a vector.
@param a the vector with the elements to merge
@param from the start of the first range
@param mid the end of the first range
@param to the end of the second range
*/
void merge(vector& a, int from, int mid, int to)
{
int n = to - from + 1; // Size of the range to be merged
// Merge both halves into a temporary vector b
vector b(n);

int i1 = from;
// Next element to consider in the first half
int i2 = mid + 1;
// Next element to consider in the second half
int j = 0; // Next open position in b
// As long as neither i1 nor i2 is past the end, move the smaller
// element into b
while (i1 <= mid && i2 <= to)
{
if (a[i1] < a[i2])
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++;
}

// Note that only one of the two while loops below is executed

// Copy any remaining entries of the first half
while (i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
// Copy any remaining entries of the second half
while (i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}

// Copy back from the temporary vector
for (j = 0; j < n; j++)
a[from + j] = b[j];
}

/**
Sorts the elements in a range of a vector.
@param a the vector with the elements to sort
@param from start of the range to sort
@param to end of the range to sort
*/
void merge_sort(vector& a, int from, int to)
{
if (from == to) return;
int mid = (from + to) / 2;
// Sort the first and the second half
merge_sort(a, from, mid);
merge_sort(a, mid + 1, to);
merge(a, from, mid, to);
}

int main()
{
rand_seed();
vector v(20);
for (int i = 0; i < v.size(); i++)
v[i] = rand_int(1, 100);
print(v);
merge_sort(v, 0, v.size() - 1);
print(v);
return 0;
}

ch11/selsort/selsort.cpp #include 3 #include "util.h" 4 k * Gets the position of the smallest element in a vector range. Qparam a the vector @param from the beginning of the range @param to the end of the range @return the position of the smallest element in 6 7 8 9 10 11the range a[from]...a[to] 12*/ 13 int min-position(vector

Explanation / Answer

Answer:

Insertion sort in c++ with double,string,int values code

#include <stdlib.h>

#include<iostream>
using namespace std;
template<class T>
void display(T* a,int n)
{

for(int i=0;i<n;i++)
{
cout<<" "<<a[i];
}
cout<<endl;
}
template<class T>
void arrange(T*a,int n)
{
int j = 0;
for(int i=1;i<n;i++)
{
T temp=a[i];
for( j=i-1;j>=0 && a[j]>temp ;j--)
{
a[j+1]=a[j];
j = j-1;
}

a[j+1]=temp;
}
}
int main()
{
int a[]={12,11,15,13,17,14,16,19,18};
cout<<"Before sorting ";
display(a,9);
arrange(a,9);
cout<<"After sorting ";
display(a,9);

char ch[]={'b','d','a','f','h','c','e','i','j'};
cout<<"Before sorting ";
display(ch,9);
arrange(ch,9);
cout<<"After sorting ";
display(ch,9);
arrange(ch,9);

double k[]={7.88,9.19,4.65,2.98,3.12,6.65,1.98,5.55,8.98};
cout<<"Before sorting ";
display(k,9);
arrange(k,9);
cout<<"After sorting ";
display(k,9);
arrange(k,9);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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