1. Write a program that will allow a user the opportunity to compare and analyze

Question

1. Write a program that will allow a user the opportunity to compare and analyze the efficiency of several sorting algorithms. The program will sort integer arrays of size 10, 100 and 1,000 respectively using the bubble, selection and insertion sort algorithms. The program should output in a tabular form the name of the algorithm, size of the array, number of comparisons and number of swaps. You should incorporate passing an entire array through to a function at some point in your program.

This program needs to be created using C (Visual Studio).

Explanation / Answer

#include <iostream>
#include <string>
using namespace std;

int swapCount =0;
int Comparisons =0;

void bubble_sort(int list[], int size)
{
    swapCount =0;
   Comparisons =0;
    int temp;
    for(int i=0; i<size; i++)
    {
        for(int j=size-1; j>i; j--)
        {
            if(list[j]<list[j-1])
            {
                Comparisons++;
                swapCount++;
                temp=list[j-1];
                list[j-1]=list[j];
                list[j]=temp;
            }
        }
    }
}

void insertion_sort(int list[], int size)
{
    swapCount =0;
   Comparisons =0;
    for(int j=1;j<size;j++)
    {
       int key=list[j];
        int i = j-1;
        while(i>-1 and list[i]>key)
        {
            Comparisons++;
            swapCount++;
            list[i+1]=list[i];
            i=i-1;
        }
        list[i+1]=key;
    }
}

void PrintArray(string name,int a[],int size)
{
     cout<<name<< "      " <<size << "         "<< Comparisons << "       "<< swapCount<< " ";
     for (int i = 0; i < size; ++i)
     {
        /* code */
        // cout<<a[i]<<" ";
     }
}
void selection_sort(int a[],int size)
{
   Comparisons = 0;
   swapCount = 0;
   int temp;
   for(int j=0;j<size;++j)
       for(int i=j+1;i<size;++i)
       {
           if(a[j]>a[i])
           {
               Comparisons++;
               swapCount++;
               temp=a[j];
               a[j]=a[i];
               a[i]=temp;
           }
   }
}

int main(){
   int size;
   int A[1000];
   cout<<" Enter the size of the Array: ";
   cin>>size;
   for (int i = 0; i < size; ++i)
   {
       cin>>A[i];
   }
   cout<<"Algorithm:     ArraySize:      #Comparisons    #swaps ";
  
   selection_sort(A,size);
   PrintArray("selection_sort",A,size);
   bubble_sort(A,size);
   PrintArray("bubble_sort",A,size);
   insertion_sort(A,size);
   PrintArray("insertion_sort",A,size);
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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