(Bubble Sort) Implement bubble sort—another simple yet inefficient sorting technique. It is called bubble sort or sinking sort because smaller values gradually “bubble” their way to the top of the vector (i.e., toward the first element) like air bubbles rising in water, while the larger values sink to the bottom (end) of the vector. The technique uses nested loops to make several passes

Question

through the vector. Each pass compares successive pairs of elements. If a pair is in increasing order (or the values are equal), the bubble sort leaves the values as they are. If a pair is in decreasing order, the bubble sort swaps their values in the vector. The first pass compares the first two element values of the vector and swaps them if necessary. It then compares the second and third element values in the vector. The end of this pass compares the last two element values in the vector and swaps them if necessary. After one pass, the largest value will be in the last element. After two passes, the largest two values will be in the last two ele- ments. Explain why bubble sort is an O(n2) algorithm.

What will be an ideal response?

Answer 1

```
// This program sorts a vector's values into ascending order.
#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; // temporary location used to swap vector elements

cout << "Data items in original order\n";

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

// bubble sort
// loop to control number of passes
for ( int pass = 0; pass < SIZE - 1; pass++ )
{
// loop to control number of comparisons per pass
for ( int j = 0; j < SIZE - 1; j++ )
{
// compare side-by-side elements and swap them if
// first element is greater than second element
if ( a[ j ] > a[ j + 1 ] )
{
hold = a[ j ];
a[ j ] = a[ j + 1 ];
a[ j + 1 ] = hold;
} // end if
} // end for
} // end for

cout << "\nData items in ascending order\n";

// output sorted vector
for ( int k = 0; k < SIZE; k++ )
cout << setw( 4 ) << a[ k ];

cout << endl;
return 0;
} // end main
```
Data items in original order
2 6 4 8 10 12 89 68 45 37
Data items in ascending order
2 4 6 8 10 12 37 45 68 89