(Enhanced Bubble Sort) Make the following simple modifications to improve the perfor- mance of the bubble sort you developed in Exercise 19.5:

Question

a) After the first pass, the largest value is guaranteed to be in the highest-numbered element of the vector; after the second pass, the two highest values are “in place”; and soon. Instead of making nine comparisons (for a 10-element vector) 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 vector may already be in the proper order or near-proper order, so why make nine passes (of a 10-element vector) 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

```
#include
#include
#include
using namespace std;

int main()
{
const int SIZE = 10;
int data[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };

vector < int > a; // declare vector< int > to sort

// fill the vector with values
for ( int i = 0; i < SIZE; i++ )
a.push_back( data[ i ] );

int hold;
int numberOfComp = 0; // number of comparisons made
int comp; // used to control for loop and for subscripts

// display original, unsorted vector
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 vector
for ( int pass = 1; pass < SIZE; pass++ )
{
cout << "After pass " << pass - 1 << ": ";

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

// compare adjacent vector 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 vector value
} // end outer for

// diplay vector 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;
return 0;
} // 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
#include
#include
using namespace std;

int main()
{
const int SIZE = 10;
int data[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };

vector < int > a; // declare vector< int > to sort

// fill the vector with values
for ( int i = 0; i < SIZE; i++ )
a.push_back( data[ i ] );

int hold;
int numberOfComp = 0; // number of comparisons made
int comp; // used to control for loop and for subscripts
bool swapCheck = true; // was a swap made?

// display original, unsorted vector
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 vector
for ( int pass = 1; pass < SIZE && swapCheck; pass++ )
{
cout << "After pass " << pass - 1 << ": ";
swapCheck = false; // assume no swaps will be made

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

// compare adjacent vector elements
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 vector value
} // end outer for

// diplay vector 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;
return 0;
} // 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
Data items in ascending order
2 4 6 8 10 12 37 45 68 89
Number of comparisons = 30