Как правильно переделать алгоритм сортировки выбора в пузырьковую сортировку? - PullRequest
Новая
       47

Как правильно переделать алгоритм сортировки выбора в пузырьковую сортировку?

0 голосов
/ 03 апреля 2019

Я пытаюсь преобразовать сортировку выбора в сортировку пузырьков. Я сделал это успешно? Если нет, что мне нужно сделать, чтобы исправить эту проблему?

Мне кажется, я правильно его преобразовал.

Покушение 

// 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;
  }

Цель - преобразовать сортировку выбора в сортировку по пузырькам. У меня есть оригинальный код, который у меня был до попытки преобразования, если это поможет.

1 Ответ

1 голос
/ 03 апреля 2019

Пузырьковая сортировка заменяет только соседние элементы, поэтому, когда вы тестируете несмежные элементы, вы отклоняетесь от пузырька. Самая простая форма пузырьковой сортировки имеет такую ​​форму. 

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]);
        }
    }
}

Мы можем заметить, что после первого прохода максимальное значение должно находиться в нужном месте, и аналогично после второго прохода второе по величине значение находится на своем месте и т. Д. Это позволяет нам настраивать границы внутреннего цикла. 

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]);
        }
    }
}
...