Question

c++

• programming question: Use the random number generator in class Random to store a list of 1000 random integer values in an array.  
• Create 3 arrays using this method.
• Apply each of the insertion, bubble, selection and shell sort algorithms to each array.
• Determine the number of comparisons and exchanges for each sort algorithm for each array.
• create table to print out the results.

	first	array	second	array	third	array
	comparisons	exchanges	comparisons	exchanges	comparisons	exchanges
insertion
bubble
selection
shell

Answer 1

Here is the solution to above problem in C++. Please read the code comments for more information

C++ CODE

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

//bubble sort algorithm
void bubbleSort(int a[],int &cmp,int &swaps)
{
  
   for(int i=0;i<1000;++i)
   {
       for(int j=0;j<1000-i-1;++j)
       {
           cmp++;
           if(a[j]<a[j+1])
           {
               swaps++;
              
               int temp=a[j];
               a[j]=a[j+1];
               a[j+1]=temp;
           }
       }
   }
}

//insertion sort
void insertionSort(int a[], int &cmp,int &swaps)
{
int temp;
   int j;
for (int i = 1; i < 1000; i++)
{
temp = a[i];
j = i - 1;
  
while (j >= 0 && a[j] > temp)
{
   cmp++; //comparsions plus by 2
a[j + 1] = a[j];
swaps++;
j = j - 1;
}
//only one swap
a[j + 1] = temp;
}
}

//selection sort
void selectionSort(int a[], int &cmp,int &swaps)
{
int temp;

for (int i = 0; i <999; i++)
{
       temp = i;
for (int j = i+1; j < 1000; j++)
{
cmp++;
if (a[j] < a[temp])
temp = j;
       }
    int temp2 = a[temp];
    a[temp]=a[i];
    a[i]=temp2;
swaps++;
}
}
  

int main()
{
   srand(time(0));
   //thre array
   int a1[1000];
   int a2[1000];
   int a3[1000];
   //initialize the array
   for(int i=0;i<1000;++i)
   {
       a1[i]=rand()%1000;
       a2[i]=rand()%1000;
       a3[i]=rand()%1000;
      
   }
  
   cout<<"       FIRST ARRAY        SECOND ARRAY        THIRD ARRAY\n";
   cout<<"       CMP   EXH       CMP   EXH       CMP   EXH\n";
   cout<<"Insertion ";
   cout<<"   ";
   int cmp=0;
   int swaps=0;
   insertionSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   insertionSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   insertionSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   cout<<endl;
   cout<<"Selection ";
   cout<<"   ";
   selectionSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   selectionSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   selectionSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   cout<<endl;
   cout<<"Bubble   ";
   cout<<"   ";
   bubbleSort(a1,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   bubbleSort(a2,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
   bubbleSort(a3,cmp,swaps);
   cout<<cmp<<"   "<<swaps<<"       ";
   cmp=0;
   swaps=0;
  
}

SCREENSHOT OF OUTPUT