Write a C++ program to create 2 identical arrays, list1, and list2 – each list o

Question

Write a C++ program to create 2 identical arrays, list1, and list2 – each list of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort and outputs the number of comparisons and item assignments made by each sorting algorithm. Hint: You need to create a random array and then copy it to end up with two identical lists (List1, List2). These two lists must be identical. You will need to sort List1 using bubble sort, and sort the second list List2 using the selection sort algorithm. Finally, you will need to output the number of comparisons and item assignments made by each sorting algorithm. Plea se note that the array should be randomly generated and you can do that by using the random function: rand() from the library.

Explanation / Answer

ScreenShot

-------------------------------------------------------------------------------

Program

//Header files for I/O and random generatio
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
//Function prototype
void bubbleSort(int num[],int size, int &comparisons, int &itemAssignments);
void selectionSort(int num[], int size, int &comparisons, int &itemAssignments);
int main()
{
   //Arrays for random generation and copying
   int arr[5000];
   int list1[5000];
   int list2[5000];
   //Length of the array and comparison variables
   int size = 5000,bubbleSortComparison = 0, selectionSortComparison = 0, bubbleSortAssignment = 0, selectionSortAssignment = 0;;
   //Random array creation
   srand(time(0));
   for (int i = 0; i < size; i++)
       arr[i] = rand();
   //Copy array into list1 and list2
   for (int i = 0; i < size; i++)
       list1[i] = list2[i]=arr[i];
   //call bubblesort and get comparison and assignment value
   bubbleSort(list1, 5000, bubbleSortComparison, bubbleSortAssignment);
   cout << "Number of comparisons in Bubble sort:" << bubbleSortComparison << endl;
   cout << "Number of item assignments in Bubble sort: " << bubbleSortAssignment << endl;
   //call selection sort and get comparison and assignment value
   selectionSort(list2, 5000, selectionSortComparison, selectionSortAssignment);
   cout << "Number of comparisons in Selection sort:" << selectionSortComparison << endl;
   cout << "Number of item assignments in Selection sort: " << selectionSortAssignment << endl;
   return 0;
}
//Bubble sort expansion
void bubbleSort(int arr[], int size, int &comparisons, int &assignments)
{
   //Variable for sort check
   bool isSorted = false;
   //loop until get sorted
   while (!isSorted) {
       isSorted = true;
       for (int i = 0; i<size - 1; i++)
       {
           //increment comparisons by one
           comparisons++;
           if (arr[i] > arr[i + 1])
           {
               //isSorted = false;
               int temp = arr[i];
               arr[i] = arr[i + 1];
               arr[i + 1] = temp;
               //increment assignment 3 because 3 assignment happen above
               assignments += 3;
           }
       }
   }
}
//Selection sort expansion
void selectionSort(int num[], int size, int &comparisons, int &assignments) {
   //smallest value index
   int minIndex;
   //Loop for sorting
   for (int i = 0; i < size-1; i++) {
       minIndex = i;
      
       for (int index = i + 1; index < size; index++) {
           // count comparison
           comparisons++;
           if (num[index] < num[minIndex]) {
               minIndex= index;
           }
       }
       int temp = num[minIndex];
       num[minIndex] = num[i];
       num[i] = temp;
       //increment assignments by three
       assignments +=3;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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