19.5 C++ How to Program (8th Edition) By Paul Deitel, Harvey Deitel

(Bubble Sort) Implement bubble sort—another simple yet inefficient sorting technique. It’s 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 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 elements. Explain why bubble sort is an O(n2) algorithm.

Solution:

 
#include <vector>
using std::vector;
 
class Bubble
{
public:
   Bubble(int);
   void sort();
   void displayElements();
private:
   int size;
   vector<int> data;
};
 

 
// Bubble main.cpp
 
#include <iostream>
using std::endl;
using std::cout;
 
#include "Bubble.h"
 
int main()
{
   int vectorSize = 10;
 
   //new vector
   Bubble newVector(vectorSize);
 
   // display new vector
   cout << "Unsorted vector" << endl;
   newVector.displayElements();
 
   // sort vector
   newVector.sort();
 
   // display new vector
   cout << "\nSorted vector" << endl;
   newVector.displayElements();
 
}
 
// Bubble.cpp
 
#include <iostream>
using std::cout;
 
#include <cstdlib>
using std::rand;
using std::srand;
 
#include <ctime>
using std::time;
 
#include "Bubble.h"
 
// fill vector with constructor
Bubble::Bubble(int vectorSize)
{
   size = vectorSize;
   srand(time(0));
 
   for(int i = 0; i < size; i++)
   {
      data.push_back(rand() % 100);
   }
}
 
//display elements
void Bubble::displayElements()
{
   for(int j = 0; j < size; j++)
   {
      cout << data[j] << " ";
   }
}
 
// sort function
void Bubble::sort()
{
   int buf;
   int size1 = size;
 
   for(int i = 1; i < size1; size1--)
   {
      for(int j = 1; j < size1; j++)
      {
         if(data[j] < data[j - 1])
         {
            buf = data[j];
            data[j] = data[j - 1];
            data[j - 1] = buf;
         }
      }
 
   }
}
 

Explain why bubble sort is an O(n2) algorithm.

* n2 comparisons required to sort n elements.

* n additional elements require n2 additional comparisons.