Question

A template (generic) function for insertion sort is given to you.

Part-1: design a function to compare 2 strings using case-insensitive

comparison,

a function to test if 2 records are not equal (using case-insensitive

string comparison).

Part-2: define your own compare function required by the template

insertionSort function.

#include <iostream>

#include <string>

#include <cstdlib>

#include <iomanip>

#include <ctime>

#define BASE 1000000000LL // long long int

using namespace std;

struct record

{

long long value;

string str;

};

// Part-1: case-insensitive string comparison, and operator!=()

bool operator!=(const record& r1, const record& r2)

{

// Test if r1 is NOT equal to r2.

// Strings are compared using case-insensitive comparison.

return true; // dummy return statement

}

// Part-2: compare function required by the template insertionSort and bubbleSort

functions

// Part-3: your template bubble sort function

// Part-4: compare function required by qsort

template<class Type>

void insertionSort(Type *x, int n, int (*compare)(const Type&, const Type&))

{

for (int i = 1; i < n; i++)

{

Type t = x[i];

int j;

for (j = i-1; j >= 0 && compare(x[j], t) > 0; j--)

x[j+1] = x[j];

x[j+1] = t;

}

}

void test_insertionSort(record *a, int n)

{

// Sort the list of record by value, and then by length of str,

// and then by str value using case-insensitive comparison.

clock_t begin, end;

double elapsedTime;

cout << "insertion sort: n = " << n << endl;

begin = clock();

// *** add your statement to sort the array a[] using insertionSort

end = clock();

elapsedTime = (double)(end - begin)/CLOCKS_PER_SEC;

cout << "Elapsed time = " << elapsedTime << " seconds" << endl << endl;

}

Answer 1

#include <iostream>

#include <string>

#include <cstdlib>

#include <iomanip>

#include <ctime>

#define BASE 1000000000LL // long long int

using namespace std;

struct record

{

long long value;

string str;

};

// Part-1: case-insensitive string comparison, and operator!=()

bool operator!=(const record& r1, const record& r2)

{
string str1 = r1.str;
string str2 = r2.str;
char ch1,ch2;

if(str1.length()!=str2.length())return false;
else {
   for(int i=0;i<str1.length();i++){
       ch1 = str1[i];
       ch2 = str2[i];
       if(ch1>='A'&&ch1<='Z')ch1=ch1-'A'+'a';
       if(ch2>='A'&&ch2<='Z')ch2=ch2-'A'+'a';
      
       if(ch1!=ch2)return false;
   }
}

return true; // dummy return statement

}

// Part-2: compare function required by the template insertionSort and bubbleSort
template<class Type>
int compare (const Type& r1, const Type& r2){
   if(r1.value > r2.value) return 1;
   return 0;
}

// Part-3: your template bubble sort function

template<class Type>

void bubbleSort(Type *x, int n, int (*compare)(const Type&, const Type&))

{

for(int i=n-1;i>=0;i--){
       for(int j=0;j<i;j++){
           if(compare(x[j], x[j+1]) > 0){
               Type temp=x[j];
               x[j]=x[j+1];
               x[j+1]=temp;
           }
       }
   }

}

// Part-4: compare function required by qsort

template<class Type>

void insertionSort(Type *x, int n, int (*compare)(const Type&, const Type&))

{

for (int i = 1; i < n; i++)

{

Type t = x[i];

int j;

for (j = i-1; j >= 0 && compare(x[j], t) > 0; j--)

x[j+1] = x[j];

x[j+1] = t;

}

}

void test_insertionSort(record *a, int n)

{

// Sort the list of record by value, and then by length of str,

// and then by str value using case-insensitive comparison.

clock_t begin, end;

double elapsedTime;

cout << "insertion sort: n = " << n << endl;

begin = clock();

// *** add your statement to sort the array a[] using insertionSort
insertionSort(a, n,&compare);

end = clock();

elapsedTime = (double)(end - begin)/CLOCKS_PER_SEC;

cout << "Elapsed time = " << elapsedTime << " seconds" << endl << endl;

}