Проблема алгоритма сортировки пузырьков в C++

Question

В моем математическом задании мне необходимо разработать несколько форм алгоритмов сортировки, и я решил начать с «простого»: сортировки пузыря.

У меня есть два списка:

3.3 5 9.89 -6 

и

-564 1340 42 129 858 1491 1508 246 -1281 655 1506 306 290 -768 116 765 -48 -512 2598 42 2339 

Я могу сортировать первый легко, но есть проблема в середине сортировки для второго.

Вот мой маленький кусок кода, который заботится о сортировке.

int  bubbleSort(std::list<double> list) 
{ 
    std::list<double>::iterator it; // First iterator i 
    std::list<double>::iterator it2; // Second iterator i+1 
    int       comp = 0; 

    it = list.begin(); 
    it2 = list.begin(); 
    it2++; 
    for (int i = list.size() - 1; i > 0; --i) 
    { 
     for (int j = 0; j < i; j++) 
     { 
      comp++; 
      if (*it2 < *it) // If my second item is smaller than my first one, swap them 
      { 
       std::swap(*it2, *it); 
       it = list.begin(); 
       it2 = list.begin(); 
       it2++; 
       break; 
      } 
      it++; 
      it2++; 
     } 
    }  
    return comp; 
} 

Вот outputed список я получаю, как вы можете видеть, что это перестает быть отсортирован в середине пути:

-1281 -564 42 129 246 858 1340 1491 655 1508 1506 306 290 -768 116 765 -48 -512 2598 42 2339 

Где я ошибся в моем алгоритме?

Answer 1

Это рабочий код для сортировки пузырей, который вы, возможно, ищете.

1. Сначала вы должны передать список по реф не ценят
2. пузыря до максимального значения в конце списка.

3. Правильно инициализируйте его, it2 внутри сначала для цикла.

   #include <bits/stdc++.h> 
   using namespace std; 
   
   int bubbleSort(std::list<double> &list) { 
   std::list<double>::iterator it; // First iterator i 
   std::list<double>::iterator it2; // Second iterator i+1 
   int       comp = 0; 
   
   for (int i = list.size() - 1; i > 0; --i) { 
       it = list.begin(); 
       it2 = list.begin(); 
   
       it2++; 
       for (int j = 0; j < i; j++) { 
       comp++; 
       if (*it2 < *it) { // If my second item is smaller than my first one, swap them 
        std::swap(*it2, *it); 
        //it = list.begin(); 
        //it2 = list.begin(); 
        //it2++; 
        //break; 
       } 
       it++; 
       it2++; 
       } 
   } 
   return comp; 
   } 
   
   int main() { 
   list<double> l; 
   int n; 
   cin >> n; 
   while (n--) { 
       double tmp; 
       cin >> tmp; 
       l.push_back(tmp); 
   } 
   bubbleSort(l); 
   for (list<double>::iterator i = l.begin(); i != l.end(); i++) { 
       cout << *i << " "; 
   } 
   cout << endl; 
   }