Question

Write a program that creates three identical arrays, list1, list2, and list3, of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm

Note: (Complete Programming Exercise #15 on page 1345. Submit a screen shot testing with 20 numbers, 500 numbers, 1,000 numbers. Show the output of the arrays of 20 so you can see they are in order. Save the file with your FirstInitial LastName Lab10.

Include also three source file: main.cpp, function.h,function.cpp)

C++ Program Design Including data Structures,7th Edition, D.S Malik

Answer 1

Below is the code for above problem, with screenshots of the code and sample output.

If you have any doubts, feel free to ask in comments.

function.h

#include <iostream>

using namespace std;

//function to do bubble sort
void bubbleSort(int[], int);

//function to do selection sort
void selectionSort(int[], int);

//function to do insertion sort
void insertionSort(int[], int);

//function to print array
void printArray(int[], int);

function.cpp

#include "function.h"

#include <iostream>
#include <stdlib.h>

using namespace std;

//function that does bubble sort
void bubbleSort(int arr[], int n) {
  
   int numOfComparisons = 0;
   int numOfAssignments = 0;
  
    for (int i = 0; i < n - 1; i++) {
      
       for (int j = 0; j < n - i - 1; j++) {
          
           numOfComparisons++;
           if (arr[j] > arr[j + 1]) {
              
               int temp = arr[j];
               numOfAssignments++;
               arr[j] = arr[j + 1];
               numOfAssignments++;
               arr[j + 1] = temp;
               numOfAssignments++;
            }
        }
    }
  
    cout<<"Doing Bubble Sort with "<<n<<" elements...\n";
  
    cout<<"Number of Comparisons = "<<numOfComparisons<<endl;
  
    cout<<"Number of Assignments = "<<numOfAssignments<<endl<<endl;
}

//function that does selection sort
void selectionSort(int arr[], int n) {
  
   int numOfComparisons = 0;
   int numOfAssignments = 0;
  
    for (int i = 0; i < n - 1; i++) {
      
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
          
           numOfComparisons++;
              if (arr[j] < arr[min_idx]) {
                 
               min_idx = j;
           }
        }
      
        if (min_idx != i) {
          
           int temp = arr[min_idx];
           numOfAssignments++;
           arr[min_idx] = arr[i];
           numOfAssignments++;
           arr[i] = temp;
           numOfAssignments++;  
       }
    }
  
    cout<<"Doing Selection Sort with "<<n<<" elements...\n";
  
    cout<<"Number of Comparisons = "<<numOfComparisons<<endl;
  
    cout<<"Number of Assignments = "<<numOfAssignments<<endl<<endl;
}

//function that does insertion sort
void insertionSort(int arr[], int n) {
  
   int numOfComparisons = 0;
   int numOfAssignments = 0;
  
   for (int i = 1; i < n; i++) {
      
        int key = arr[i];
        int j = i - 1;
      
       numOfComparisons++;
      
        while (j >= 0 && arr[j] > key) {
          
            arr[j + 1] = arr[j];
            numOfAssignments++;
            j = j - 1;
            numOfAssignments++;
        }
      
        arr[j + 1] = key;
       numOfAssignments++;
    }
  
  
    cout<<"Doing Insertion Sort with "<<n<<" elements...\n";
  
    cout<<"Number of Comparisons = "<<numOfComparisons<<endl;
  
    cout<<"Number of Assignments = "<<numOfAssignments<<endl<<endl;
}

//function that prints the content of an array
void printArray(int arr[], int n) {
  
   for (int i = 0; i < n; i++) {
       cout<<arr[i]<<" ";
   }
   cout<<endl;
  
   cout<<"-----------------------------------------------------------------------------------------------------------------------------\n";
}

main.cpp

#include "function.cpp"

#include <iostream>
#include <stdlib.h>

using namespace std;

int main() {
  
   //define three arrays
   int arr1[1000];
   int arr2[1000];
   int arr3[1000];
  
   //initialize arrays with random values
   for(int i = 0; i < 20; i++) {

       int val = (rand() % 100) + 1;
      
       arr1[i] = val;
       arr2[i] = val;
       arr3[i] = val;

    }
  
    cout<<"Array 1, before sorting = ";
    printArray(arr1, 20);
  
   bubbleSort(arr1, 20);
  
    cout<<"Array 1, after sorting = ";
    printArray(arr1, 20);
  
    cout<<"Array 2, before sorting = ";
    printArray(arr2, 20);
  
    selectionSort(arr2, 20);
  
    cout<<"Array 2, after sorting = ";
    printArray(arr2, 20);
  
    cout<<"Array 3, before sorting = ";
    printArray(arr3, 20);
  
    insertionSort(arr3, 20);
  
    cout<<"Array 3, after sorting = ";
    printArray(arr3, 20);
  
   for(int i = 0; i < 500; i++) {

       int val = (rand() % 1000) + 1;
      
       arr1[i] = val;
       arr2[i] = val;
       arr3[i] = val;

    }
  
   bubbleSort(arr1, 500);
  
    selectionSort(arr2, 500);
  
    insertionSort(arr3, 500);
  
    for(int i = 0; i < 1000; i++) {

       int val = (rand() % 1000) + 1;
      
       arr1[i] = val;
       arr2[i] = val;
       arr3[i] = val;

    }
  
   bubbleSort(arr1, 1000);
  
    selectionSort(arr2, 1000);
  
    insertionSort(arr3, 1000);
      
}

Screenshot of function.h :

Screenshots of function.cpp:

1)

2)

3)

Screenshots of main.cpp :

1)

2)

3)

Screenshot of the sample output :