You are to write a C++ program to compare two sorting algorithms and compare two

Question

You are to write a C++ program to compare two sorting algorithms and compare two searching algorithms by running the algorithms and collecting data on each. Your data for sorting and searching will be strings of 25 characters in length. You are to have your program run, compute and print all the results in one run, not multiple runs. (You are not to run your program once for each data set.)

First Part: The two sorts to compare are the Bubble Sort and the Selection Sort.   You are to test your sorts against different set of strings. Each sort will sort six sets of data, 1000 strings, then 3000 strings, 5000, 7000, 9000 and 11000 strings. You will compare how well each sort did with the different data sizes and show results. I would like to see a plot of the results. A table format showing results will do. Use the

Explanation / Answer

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

void swap(string arr[], int i, int j){
   string temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}

void bubbleSort(string arr[], int size){
   int i = 0, j = 0;
   for(i = 0; i < size - 1; ++i){
       for(j = 0; j < size - i - 1; ++j){
           if(arr[j] > arr[j + 1]){
               swap(arr, j, j + 1);
           }
       }
   }
}

void selectionSort(string arr[], int size){
   int i = 0, j = 0, mind = -1;
   string min = "";
   for(i = 0; i < size - 1; ++i){
       min = arr[i];
       mind = i;
       for(j = i + 1; j < size; ++j){
           if(arr[j] < min){
               mind = j;
               min = arr[j];
           }
       }
       if(mind != i){
           swap(arr, i, mind);
       }
   }
}

int search(string arr[], string str, int size){
   for(int i = 0; i < size; ++i){
       if(arr[i] == str){
           return i;
       }
   }
   return size;
}

int bsearch(string arr[], string str, int size)
{
   int Mid,Lbound=0,Ubound=size-1;
   int count = 1;
   while(Lbound<=Ubound)
   {
       Mid=(Lbound+Ubound)/2;
       if(str>arr[Mid])
           Lbound=Mid+1;
       else if(str<arr[Mid])
           Ubound=Mid-1;
       else{
           return count;
       }
       count++;
   }

   return count;
}

int main(){
   string arr11[1000];
   string arr12[1000];
   string arr31[3000];
   string arr32[3000];
   string arr51[5000];
   string arr52[5000];
   string arr71[7000];
   string arr72[7000];
   string arr91[9000];
   string arr92[9000];
   string arr111[11000];
   string arr112[11000];
   for(int i = 1000; i <= 11000; i += 2000){
       for(int j = 0; j < i; ++j){
           string temp1 = "";
           string temp2 = "";
           for(int k = 0; k < 25; ++k){
               temp1 += (char)(rand() % 26 + 65);
               temp2 += (char)(rand() % 26 + 65);
           }
           if(i == 1000){
               arr11[j] = temp1;
               arr12[j] = temp2;
           }
           else if(i == 3000){
               arr31[j] = temp1;
               arr32[j] = temp2;
           }
           else if(i == 5000){
               arr51[j] = temp1;
               arr52[j] = temp2;
           }
           else if(i == 7000){
               arr71[j] = temp1;
               arr72[j] = temp2;
           }
           else if(i == 9000){
               arr91[j] = temp1;
               arr92[j] = temp2;
           }
           else if(i == 11000){
               arr111[j] = temp1;
               arr112[j] = temp2;
           }
       }
   }
   clock_t time1, time2;
   double diffTime;
   double diffTime1[6];
   double diffTime2[6];
   int k = 0;
   for(int i = 1000; i <= 11000; i += 2000){
       if(i == 1000){
           time1 = clock();
           bubbleSort(arr11, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr12, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       else if(i == 3000){
           time1 = clock();
           bubbleSort(arr31, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr32, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       else if(i == 5000){
           time1 = clock();
           bubbleSort(arr51, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr52, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       else if(i == 7000){
           time1 = clock();
           bubbleSort(arr71, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr72, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       else if(i == 9000){
           time1 = clock();
           bubbleSort(arr91, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr92, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       else if(i == 11000){
           time1 = clock();
           bubbleSort(arr111, i);
           time2 = clock();
           diffTime1[k] = difftime(time2, time1);
           time1 = clock();
           selectionSort(arr112, i);
           time2 = clock();
           diffTime2[k] = difftime(time2, time1);
       }
       ++k;
   }
   cout << "Size " << "Bubble Sort " << "Selection Sort" << endl;
   for(int i = 0; i < 6; ++i){
       cout << (1000 + (2000 * i)) << " " << diffTime1[i] << " " << diffTime2[i] << endl;
   }
   int nC = 0;
   int bC = 0;
   for(int i = 0; i < 2000; ++i){
       nC += search(arr111, arr111[rand() % 11000], 11000);
       bC += bsearch(arr111, arr111[rand() % 11000], 11000);
   }
   cout << "Average probes for linear search is " << nC / 2000.0 << endl;
   cout << "Average probes for binary search is " << bC / 2000.0 << endl;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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