Bubble sort can be improved to run more efficiently when the

Bubble sort can be improved to run more efficiently when the input is nearly in order by testing whether no exchange at all are performed on one of the passes. a. (15%) Modify the algorithm so that it stops when no exchange are performed on one of the passes. b. (20%) Write a program to compare the actual running times of the original Bubble Sort and the modified algorithm. Your code should test the sorting methods for different size of N (10, 100, 1000, 4000, 8000, 10000, 25000, 50000, 75000 and 100000) and different types of data (sorted in ascending order, sorted in descending order, and unsorted). Your output should contain tables of the actual running time for each algorithm.

Solution

Hi,

Following is the C++ programme which has three function

1. optimizeBubbleSort() : which is optimize implementation of bubble sort.

2. BubbleSort() : which is implementation of bubble sort.

3. main() : Show the computation of time used by both the function and also generate the random array of given size n.

CODE :

#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < n; i++)

using namespace std;

void optimizeBubbleSort(int *a, int n)
{
   bool isSwap;
   int t;
for(int i=0; i<n; i++){
   isSwap = false;
for(int j=0; j<n-i-1; j++){
if(a[j] > a[j+1])
{
   isSwap = false;
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
}
}
if(isSwap) return;
}
}
void bubbleSort(int *a, int n)
{
   int t;
for(int i=0; i<n; i++){
for(int j=0; j<n-i-1; j++){
if(a[j] > a[j+1])
{
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
}
}
}
}

int main()
{
   int n = 30000;
   clock_t start, start2;

   int b[n];
   FOR(i, n) b[i] = rand(); //storing n random data in First array
   start2 = clock();
   bubbleSort(b, n);
   cout << ((double) (clock() - start2)) * 1000 / CLOCKS_PER_SEC << endl; //showing time used by bubble sort Algorithm.

   /******************/
   int a[n];
   FOR(i, n) a[i] = rand(); //storing n random data in Second array
   start = clock();
   optimizeBubbleSort(a, n);
   cout << ((double) (clock() - start)) * 1000 / CLOCKS_PER_SEC << endl; //showing time used by optimize bubble sort Algorithm.
   /***************/

   return 0;
}