Question

In C++ language, implement a class that can sort an array of numbers using all three algorithms we have seen in this course, but each method updates a “counter” value every time it accesses the array. Have it print this at the end of the sorting process. Store the array values in an “original” array so you don’t have to re-type it for different sorts (since each sort alters the array), and have the sort modify a copy.

Note: IF statements increment the counter by 1, unless they have both parameters as elements of the array being sorted. In such a case, the IF statements increment the counter by two instead.

For example, the following line would increase the value of counter by 1:

       if(array[x] > y)

This statement would increase the value by two since it accesses the array twice:

       if (array[x] < array[y])

Assignment statements and reads for printing each increase the counter value by 1.

Swap statements take up 4 accesses (read: get a and store in temp, write: set a to b (a read and a write), write: set b to temp).

Sample Output

Enter an array of 10 values.

Enter value 1: 90

Enter value 2: 33

Enter value 3: 22

Enter value 4: -7

Enter value 5: 100

Enter value 6: 8

Enter value 7: 11

Enter value 9: 12

Enter value 10: 55

Sorting a copy of the array using Bubble Sort...

Sorting a copy of the array using Selection Sort...

Sorting a copy of the array using Quick Sort...

Array has been sorted

Bubble Sort accessed the array 78 times.

Selection Sort accessed the array 99 times.

Quick Sort accessed the array 50 times.

Quick Sort had the least number of accesses.

Run the code on several different arrays and see if one algorithm is consistently faster (i.e., has less accesses than the others). Include your results in the ending comment block of your submitted code. Note that I came up with the numbers/results in the sample output at “random.” They do not represent an actual run of the code on those numbers; I want all your results to come from your code’s actual run.

Answer 1

please read the following code with comment for better understand.

//Modified sorting program
#include <iostream>
using namespace std;
//swaping function for swapping element
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//bubble sort
int bubble_sort(int arr[])
{
int i, j, temp, c=0,n=10;
for (i = 0; i < n-1; i++)   
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{   //increment by 2 because twice array searching
   c=c+2;
               swap(&arr[j], &arr[j+1]);
           }
  
   return c;
}
//selection sort
int selection_sort(int arr[])
{
int i, j, min,c=0,n=10,temp=0;
for (i = 0; i < n-1; i++)
{
min = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min])
   {
       min = j;
       //increment by 2 because twice array searching
       c=c+2;
      
           }     
  
       swap(&arr[min], &arr[i]);
  
}
  
   return c;
}
//quick sort
int count=0;
int partition (int arr[], int low, int high)
{
int pivot = arr[high],temp;
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{
i++;
           //increment for only one time
           count=count+1;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
int
quick_sort(int arr[], int low, int high)
{   
if (low < high)
{
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
return count;
}
int main(){
   int number[10],number1[10],number2[10],number3[10];
   cout<<"Enter an array of 10 values";
   for(int i=0;i<10;i++){
       cout<<"\nEnter value "<<i+1<<": ";
       cin>>number[10];
   }
   cout<<"\nSorting a copy accessed the array using Bubble Sort...";
   for(int j=0;j<10;j++){
       number1[j]=number[j];
   }
   int c_bubble_sort = bubble_sort(number1);
   cout<<"\nSorting a copy accessed the array using Bubble Sort...";
   for(int j=0;j<10;j++){
       number2[j]=number[j];
   }
   int c_selection_sort = selection_sort(number2);
   cout<<"\nSorting a copy accessed the array using Bubble Sort...";
   for(int j=0;j<10;j++){
       number3[j]=number[j];
   }
   int c_quick_sort = quick_sort(number3,0,9);
   cout<<"\nArray has been sorted";
   cout<<"\nBubble sort Accessed the array "<<c_bubble_sort<<" times.";
   cout<<"\nSelection sort Accessed the array "<<c_selection_sort<<" times.";
   cout<<"\nQuick sort Accessed the array "<<c_quick_sort<<" times.";
   if((c_quick_sort<c_selection_sort) && (c_quick_sort<c_bubble_sort)){
       cout<<"Quick sort had the least number of accesses";
   }
   else if ((c_selection_sort<c_quick_sort) && (c_selection_sort<c_bubble_sort)){
       cout<<"Selection sort had the least number of accesses";
   }
   else{
       cout<<"Bubble sort had the least number of accesses";
   }
}