Question

The bubble sort described in AS 7e is inefficient when perform on a larger array. To improve the efficiency, we have to observe the basic mechanism of Bubble Sort.

Each inner loop of the Bubble sort always move the largest item on the unsorted left side to the sorted right side.

When a list is sorted, we say the list is in ascending order by convention.

We can enhance the efficiency of traditional Bubble sort by making only one swapping per inner loop iteration. To accomplish this, the following simple modifications are applied:

1. The inner loop is to find the index of the largest item inside the unsorted region.
2. The outer loop is to swap the largest item with the rightmost unsorted item, and then the right most unsorted item becomes the newest sorted item.
3. The array started as one big unsorted region; each inner loop iteration move one unsorted item to become a sorted item.
4. The number of comparisons is the same as the standard bubble sort, however, the number of swaps are reduced to no more than once per inner loop and no more than n times for the entire sort.

Hint:
The inner loop finds the index of the largest item of the unsorted region and performs no swap operation.
The outer loop index to track the range of "unsorted region."

Example of Sorted vs Unsorted region through each inner iterations:

4, 3, 5, 7, 2, 9, 1  unsorted | sorted

4, 3, 5, 7, 2, 1| 9 (1st iteration)
4, 3, 5, 1, 2| 7, 9 (2nd iteration)
4, 3, 2, 1| 5, 7, 9 (3rd iteration)
1, 3, 2| 4, 5, 7, 9 (4th iteration)
1, 2| 3, 4, 5, 7, 9 (5th iteration)
1, 2, 3, 4, 5, 7, 9 (6th iteration)

Note:

Complexity of program is to gauge its performance of time and space. See here.

Submit

• the C++ source code and
• the test output for self validation

Answer 1

I am using an additional function printArray to print the current order of the array. and also printing the iteration count to show that maximum swappings will be n-1.

*************************************************************************************************************

#include<iostream>
using namespace std;

void printArray(int arr[],int n){
   for(int i=0;i<n;++i){
       cout<<arr[i]<<" ";
   }
   cout<<endl;
}
void bubbleSort(int arr[],int n){
   for(int i=0;i<n-1;++i){
       int index=0; //to store the maximum element in unsorted array
       for(int j=1;j<n-i;++j){
           if(arr[index]<arr[j]){
               index=j;
           }
       }
       int temp=arr[index];
       arr[index]=arr[n-1-i];
       arr[n-1-i]=temp;
       cout<<"Iteration: "<<(i+1)<<endl;
       printArray(arr,n);
   }
}

int main(){
   int arr[]={4, 3, 5, 7, 2, 9, 1};
   int n=7;
   bubbleSort(arr,n);
   cout<<"After sort: ";
   printArray(arr,n);
}

*************************************************************************************************************

You can also reduce the number of swappings by adding another if condition above swapping.

if(index!=n-1-i){

int temp=arr[index];
       arr[index]=arr[n-1-i];
       arr[n-1-i]=temp;

}

This will check whether the largest element is present at right most index of unsorted array or not. if present then no need to swap the elements.

If not present then only swap the elements.

Output:

I would like to share some other modified bubble sort where we can use when the array is partially sorted.

Here the approach is same as above but we will swap the elements in inner loop only. If there won't be any swapping happened in inner loop after some iterations then it means the array is sorted so no need to proceed further and we will simply break the loop.

void bubbleSort(int arr[],int n){
   for(int i=0;i<n-1;++i){
       bool find=true;
       for(int j=0;j<n-1-i;++j){
           if(arr[j+1]<arr[j]){
               int temp=arr[j];
               arr[j]=arr[j+1];
               arr[j+1]=temp;
               find=false;
           }
       }
       if(find)
           break;
   }
}

If you feel it as helpful and shareable share it with your friends.

If you have any doubts kindly ask me. Thank you