Using c Create an array of 100 random numbers between 0100 S

Using c++, Create an array of 100 random numbers between 0-100. Sort the array using bubble sort and insertion sort. Create two counters to keep track of the number of swap operations taken for each sort algorithm and compare them. Which sort algorithm is more efficient?

Solution

Answer:

Considering shifting and swapping as major operations.

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;

#define SIZE 100

void swap(int *xp, int *yp, int* counter)
{
int temp = *xp;
(*counter)++;
*xp = *yp;
*yp = temp;
}

int bubble_sort(int arr[]){

int i, j, counter=0;
int n = SIZE;
for (i = 0; i < n; i++)
for (j = 0; j < n-i-1; j++) //Last i elements are already in place
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1],&counter);
  
return counter;

}

int insertion_sort(int arr[])
{
int i, key, j;
int counter = 0;
int n = SIZE;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;

counter++;
}
arr[j+1] = key;
}

return counter;
}

int main(){

   int bubble_counter,insertion_counter;
   int i;
   int arr_1[SIZE],arr_2[SIZE];
  
   srand(time(NULL));
  
   for (i=0 ; i<SIZE ; i++){
       arr_1[i] = rand()%100;
       arr_2[i] = arr_1[i];
   }
  
   printf (\"Array is :\");
   for (i=0 ; i< SIZE ; i++)
       printf (\"%d \",arr_1[i]);
   printf (\"\ \");
   bubble_counter = bubble_sort(arr_1);
   insertion_counter = insertion_sort(arr_2);
  
  
   printf (\"Number of swap in Bubble sort are %d.\ Number of shifts in insertion sort are %d\ \",bubble_counter,insertion_counter);
   if (bubble_counter == insertion_counter){
       printf (\"Both are equally efficient.\");
   }else if (bubble_counter > insertion_counter){
       printf (\"Insertion sort is better than Bubble sort\");
   }else{
       printf (\"Bubble sort is better than Insertion sort\");
   }
  
  

   return 0;
}