Question

Write in C++

(Bubble Sort) implement the bubble sort algorithm - another simple yet inefficient sorting technique. its called bubble sort or sinking sort because smaller values gradually "bubble" their way to the top of the array like air bubbles rising in water, while the larger values sink to the bottom of the array. the technique uses nested loops to make several passes through the array. each pass compares successive pairs of elements. if a pair is in increasing order, the bubble sort leaves the values as they are. if a pair is in decreasing order the bubbles sort swaps their values in the array.

The First pass cp,[ares the first two elements values of the arrow and swaps them if necessary.it then compares the second and third element values in the array. the end of this pass compares the last twon elements values in the array and swamps them if neccessary. After one pass, the largest value will be in the last element, after two passesm the largest two valuyes will be in the last two elements. explain why the bubble sort is an O(n^2) algorithm

(Enhanced Bubble Sort) Make the following simple modifications to improve the performance of the bubble sort you developed previously.

a) after the first pass, the largest value is guaranteed to be in the highest- numbered element of the array after the second pass, the two highest values are "in place"; and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make only the eight necessary comparisons on the second pass, seven on the third pass, and so on.

b) the data in the array may already be in the proper order or near-proper order, so why make nine passes if fewer will suffice? modify the sort to check at the end of each pass whether any swaps have been made. if none have been made, the data must already be in the proper order, so the program should terminate. if swaps have been made, at least one more pass is needed.

Answer 1

Time Complexity is O(n²), why ?

In an array of n elements, n-1 comparisons will be made in first pass, n-2 comparisons in second pass and so on

So, total no. of comparisions -= (n-1) + (n-2) + (n-3) +............ + 3+2+1 = n(n-1) /2

= O(n²)

C++ program:

#include <iostream>
using namespace std;

//function to swap values
void swap(int *m, int *n)
{
   int temp = *m;
   *m = *n;
   *n = temp;
}

// Enhanced Bubble Sort
void bubbleSort(int array[], int size)
{
int i, j;
bool flag;
for (i = 0; i < size-1; i++)
{
   flag = false;
  
   /* j< size-i-1 will take care of the no. of comparisons in each pass. Value of i will increase in
   each pass and hence will decrease the value of size -i-1 and hence will reduce the no.of comparisons
   in next passes */
  
   for (j = 0; j < size-i-1; j++)
   {
       if (array[j] > array[j+1])
       {
       swap(&array[j], &array[j+1]);
       flag = true;
       }
   }

   // check at the end of each pass whether any swaps have been made. if none have been made,the program will terminate
   if (flag == false)
       break;
}
}

// main program
int main()
{
   int i;
   int array[] = {14, 21, 5, 20, 77, 1, 9};
   int size = sizeof(array)/sizeof(array[0]);
   bubbleSort(array, size);
   cout<<"Array after Sorting : ";
   for (i=0; i < size-1; i++)
   cout<<array[i]<< ", ";
   cout<<array[size-1];

   return 0;
}

OUTPUT:

Output Array after Sorting : 1, 5, 9, 14, 20, 21, 77