(Bubble Sort Enhancements) The bubble sort described in Exercise 6.11 is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort:

Question

a) After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are “in place,” and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight 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 if any swaps have been made. If none have been made, then the data must already be in the proper order, so the program should terminate. If swaps have been made, then at least one more pass is needed.

Answer 1

```
#include
#include
using namespace std;

int main()
{
const int SIZE = 10; // size of array
int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
int hold;
int numberOfComp = 0; // number of comparisons made
int comp; // used to control for loop and for subscripts

// display original, unsorted array
cout << "Data items in original order\n";
for ( int i = 0; i < SIZE; ++i )
cout << setw( 4 ) << a[ i ];

cout << "\n\n";

// begin sorting the array
for ( int pass = 1; pass < SIZE; pass++ )
{
cout << "After pass " << pass - 1 << ": ";

// traverse and compare unsorted part of array
for ( comp = 0; comp < SIZE - pass; comp++ )
{
numberOfComp++;

// compare adjacent array elements
if ( a[ comp ] > a[ comp + 1 ] )
{
hold = a[ comp ];
a[ comp ] = a[ comp + 1 ];
a[ comp + 1 ] = hold;
} // end if

cout << setw( 3 ) << a[ comp ];
} // end inner for

cout << setw( 3 ) << a[ comp ] << '\n'; // print last array value
} // end outer for

// diplay array in sorted order
cout << "\nData items in ascending order\n";

for ( int j = 0; j < SIZE; j++ )
cout << setw( 4 ) << a[ j ];

// display the number of comparisons made
cout << "\nNumber of comparisons = " << numberOfComp << endl;
} // end main
```
Data items in original order
2 6 4 8 10 12 89 68 45 37
After pass 0: 2 4 6 8 10 12 68 45 37 89
After pass 1: 2 4 6 8 10 12 45 37 68
After pass 2: 2 4 6 8 10 12 37 45
After pass 3: 2 4 6 8 10 12 37
After pass 4: 2 4 6 8 10 12
After pass 5: 2 4 6 8 10
After pass 6: 2 4 6 8
After pass 7: 2 4 6
After pass 8: 2 4
Data items in ascending order
2 4 6 8 10 12 37 45 68 89
Number of comparisons = 45
```
#include
using namespace std;

int main()
{
const int SIZE = 10; // size of array
int a[ SIZE ] = { 6, 4, 2, 8, 10, 12, 37, 45, 68, 89 };
int hold; // temporary variable used for swapping
int numberOfComp = 0; // number of comparisons made
int comp; // used to control loop and for subscripts
bool swapCheck = true; // was a swap made?

// display array in original order
cout << "Data items in original order\n";

for ( int i = 0; i < SIZE; ++i )
cout << setw( 4 ) << a[ i ];

cout << "\n\n";

// sort the array
// loop until end of array, or until no swaps have been made
for ( int pass = 1; pass < SIZE - 1 && swapCheck == true; pass++ )
{
cout << "After pass " << pass - 1 << ": ";
swapCheck = false; // assume no swaps will be made

// traverse and compare unsorted part of array
for ( comp = 0; comp < SIZE - pass; comp++ )
{
numberOfComp++;

// compare two adjacent array elements
// if swap is made, set swapCheck to true
if ( a[ comp ] > a[ comp + 1 ] )
{
hold = a[ comp ];
a[ comp ] = a[ comp + 1 ];
a[ comp + 1 ] = hold;
swapCheck = true; // a swap has been made
} // end if

cout << setw( 3 ) << a[ comp ];
} // end inner for

cout << setw( 3 ) << a[ comp ] << '\n'; // print last array value
} // end outer for

// print sorted array
cout << "\nData items in ascending order\n";

for ( int q = 0; q < SIZE; q++ )
cout << setw( 4 ) << a[ q ];
cout << "\nNumber of comparisons = " << numberOfComp << endl;
} // end main
```
Data items in original order
6 4 2 8 10 12 37 45 68 89
After pass 0: 4 2 6 8 10 12 37 45 68 89
After pass 1: 2 4 6 8 10 12 37 45 68
After pass 2: 2 4 6 8 10 12 37 45
Data items in ascending order
2 4 6 8 10 12 37 45 68 89
Number of comparisons = 24