How to correctly redesign a selection sort algorithm to a bubble sort?

Question

I am attempting to convert the selection sort to a bubble sort. Have I done so successfully? If not, what do I need to do to correct this issue?

I believe I have converted it correctly.

Attempt

// This program demonstrates how to sort and search a
// string vector using selection sort and binary search.
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Function prototypes
void bubbleSort (vector < string > &);
void swap (string &, string &);
int binarySearch (const vector < string > &, string);

int main ()
{
  string searchValue;       // Value to search for
  int position;         // Position of found value

  // Define a vector of strings.
  vector < string > names
  {
  "Lopez", "Smith", "Pike", "Jones",
      "Abernathy", "Hall", "Wilson", "Kimura",
      "Alvarado", "Harrison", "Geddes", "Irvine"};

  // Sort the vector.
  bubbleSort (names);

  // Display the vector's elements.
  cout << "Here are the sorted names:\n";
for (auto element:names)
    cout << element << endl;
  cout << endl;

  // Search for a name.
  cout << "Enter a name to search for: ";
  getline (cin, searchValue);
  position = binarySearch (names, searchValue);

  // Display the results.
  if (position != -1)
    cout << "That name is found at position " << position << endl;
  else
    cout << "That name is not found.\n";

  return 0;
}

//***********************************************************************
// The selectionSort function sorts a string vector in ascending order. *
//***********************************************************************
void bubbleSort (vector < string > &v)
{
  int minIndex;
  string minValue;

  for (int pass = 1; pass < v.size (); ++pass)
    {
      for (int index = 0; (index + 1) < v.size (); ++index)
    {
      if (v[index + 1] < v[index])
        {
          swap (v[index], v[index + 1]);
        }
    }
    }

//***************************************************
// The swap function swaps a and b in memory.       *
//***************************************************
  void swap (string & a, string & b)
  {
    string temp = a;
    a = b;
    b = temp;
  }

//***************************************************************
// The binarySearch function performs a binary search on a      *
// string vector. array, which has a maximum of size elements,  *
// is searched for the number stored in value. If the number is *
// found, its vector subscript is returned. Otherwise, -1 is    *
// returned indicating the value was not in the vector.         *
//***************************************************************

  int binarySearch (const vector < string > &v, string str)
  {
    int first = 0,      // First vector element
      last = v.size () - 1, // Last vector element
      middle,           // Mid point of search
      position = -1;        // Position of search value
    bool found = false;     // Flag

    while (!found && first <= last)
      {
    middle = (first + last) / 2;    // Calculate mid point
    if (v[middle] == str)   // If value is found at mid
      {
        found = true;
        position = middle;
      }
    else if (v[middle] > str)   // If value is in lower half
      last = middle - 1;
    else
      first = middle + 1;   // If value is in upper half
      }
    return position;
  }

The goal is to convert from a selection sort to a bubble sort. I have the original code that I had before attempting the conversion if that would help.

Answer 1

Bubble sort only swaps adjacent elements, so anywhere you test non adjacent elements you are diverging from bubble. The simplest form of bubble sort is of this form.

for (int pass = 1; pass < v.size(); ++pass) {
    for (int index = 0; (index + 1) < v.size(); ++index) {
        if (v[index + 1] < v[index]) {
            swap(v[index], v[index + 1]);
        }
    }
}

We can note that after the first pass, the maximum value must be in the right place, and similarly after the second pass the second largest value is in it's place, etc. This allows us to adjust the bounds of the inner loop.

for (int pass = 1; pass < v.size(); ++pass) {
    for (int index = 0; (index + pass) < v.size(); ++index) {
        if (v[index + 1] < v[index]) {
            swap(v[index], v[index + 1]);
        }
    }
}