Use bubble sort, selection sort, and insertion sort to sort the array of 5000 elements and count the number of comparisons and assignments done in each sorting algorithm

Introduction:

Write a program that creates three identical arrays, list1, list2, and list3 of 5,000 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.

Source: MindTap Computing for Malik's C++ Programming From Problem Analysis to Program Design, 8th Edition, [Instant Access] (8th)-Malik, chapter 16, programming exercises 16.

Solved!

The objective of the programming exercise is to create 3 identical arrays of size 5000 using rand(). Sort first using bubble sort, second using selection sort, and third using insertion sort, Find the number of comparisons and assignments done for array element in each sorting algorithm. Print number of comparisons and assignments for every three sorting algorithms.

Program Plan:

· Define header section.

· Define bubbleSort(int arr[], int n, int &countComp, int &countAssign)

· Define selectionSort(int arr[], int n, int &countComp, int &countAssign)

· Define insertionSort(int arr[], int n, int &countComp, int &countAssign)

· Define main() function.

o Set seed level for rand() srand(time(0));

o Declare 3 array int l1[MAX], l2[MAX], l3[MAX].

o Use for loop i from 0 to MAX-1.

§ Declare int number = rand();

§ Initialize all element at index i using l1[i] = l2[i] = l3[i] = number

o Declare int comp1 = 0, assign1 = 0 call to bubbleSort(l1, MAX, comp1, assign1).

o Declare int comp2 = 0, assign2 = 0 call to selectionSort (l1, MAX, comp2, assign2).

o Declare int comp3 = 0, assign3 = 0 call to insertionSort (l1, MAX, comp3, assign3).

o Print the result using cout <<.

Program:

// Objective of programming exercise create 3 identical array of size 5000 using rand().
// sort first using bubbleSort, second using selectionSort, and third using insertionSort
// find number of comparisons and assignment done for array element in each sorting algo.
// print number of comparison and assignment for each three sorting algo.

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

// define macro MAX 5000.
#define MAX 5000

using namespace std;

// bubbleSort().
void bubbleSort(int arr[], int n, int &countComp, int &countAssign)
{
    // for loop i from 0 to n-2.
    for (int i = 0; i < n - 1; i++)
    {
        // for loop j from 0 to n-2-i
        for (int j = 0; j < n - 1 - i; j++)
        {
            // increment comparison count.
            countComp++;
            // comparing adjacent
            if (arr[j] > arr[j + 1])
            {
                // increment assignment count.
                countAssign++;
                // if arr[j] > arr[j+1] then swap.
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// selectionSort().
void selectionSort(int arr[], int n, int &countComp, int &countAssign)
{
    // for loop i from 0 to n-2.
    for (int i = 0; i < n - 1; i++)
    {
        // set min_j to i.
        // min_j keep track of minimum element index in array arr[i]...arr[n-1].
        int min_j = i;
        for (int j = i + 1; j < n; j++)
        {
            // increment comparison count.
            countComp++;
            // if arr[j] is less than arr[min_j] .
            if (arr[j] < arr[min_j])
            {
                // increment assignment count.
                countAssign++;
                // assignment j to min_j.
                min_j = j;
            }
        }
        // increment assignment count.
        countAssign++;
        // swap element at index i and min_j
        swap(arr[i], arr[min_j]);
    }
}

// insertionSort().
void insertionSort(int arr[], int n, int &countComp, int &countAssign)
{
    // for loop i from 1 to n-1.
    for (int i = 1; i < n; i++)
    {
        // point is copy of element that has been inserted in sorted array arr[0]...arr[i].
        int point = arr[i + 1];
        // set j  to i-1
        int j = i - 1;
        // while j >= 0 and arr[j] > point.
        while (j >= 0 && arr[j] > point)
        {
            // increment both counter.
            countComp++;
            countAssign++;
            // assignment arr[j+1] = arr[j].
            arr[j + 1] = arr[j];
            // decrement j
            j -= 1;
        }
        // set element at index j+1 to point.
        countAssign++;
        arr[j + 1] = point;
    }
}

int main()
{
    // set seed level of rand() to time(0)
    srand(time(0));
    // create 3 list.
    int l1[MAX], l2[MAX], l3[MAX];

    // fill same random value in list.(create 3 identical array)
    for (int i = 0; i < MAX; i++)
    {
        int number = rand();
        l1[i] = l2[i] = l3[i] = number;
    }

    // call to each sorting function with corresponding list(array) as argument.
    // store each result in pair.
    int comp1 = 0, assign1 = 0;
    bubbleSort(l1, MAX, comp1, assign1);
    int comp2 = 0, assign2 = 0;
    selectionSort(l2, MAX, comp2, assign2);
    int comp3 = 0, assign3 = 0;
    insertionSort(l3, MAX, comp3, assign3);

    // print result.
    cout << "Count Of          "
         << "\tComparison"
         << "\tAssignment" << endl;
    cout << "For Bubble Sort   "
         << "\t" << comp1 << "          " << assign1 << endl;
    cout << "For Selection Sort"
         << "\t" << comp2 << "          " << assign2 << endl;
    cout << "For Insertion Sort"
         << "\t" << comp3 << "          " << assign3 << endl;

    // end.
    return 0;
}