Реализация алгоритмов (сортировка пузырьков) для упорядочивания массива

Question

Сегодня я занимался написанием программы, которая в основном сортирует вход пользователя от наибольшего к наименьшему значению и отображает информацию после сортировки. Чтобы сделать это, я просмотрел некоторые алгоритмы и наткнулся на метод сортировки пузырьков. После прочтения некоторых статей я понимаю, как это работает в принципе, поэтому я пошел дальше и рассмотрел некоторые примеры кодирования алгоритмов сортировки пузырьков и реализовал то, что я узнал из примеров в моей программе. На выходе, который я получаю, кажется, что метод сортировки пузырьков работает ... в некотором роде. Из того, что я могу сказать, алгоритм/код сортировки пузырьков, который я написал, кажется, проходит через массив один раз, а не пробегает массив до тех пор, пока все целые числа не будут отсортированы в список с наименьшим значением. Может ли кто-нибудь помочь мне просмотреть мой код (особенно раздел сортировки пузыря) и указать мне в правильном направлении?

код ниже:

#include <iostream> 

using namespace std; 

int main() { 
    int pancakes[10]; 
    int x; 
    int valueSwitched; 


    for (x = 0; x < 10; x++) { 
     cout << "Please input the number of pancakes person " << (x + 1) << " has eaten.\n"; 
     cin >> pancakes[x]; 
    } 

    for (int x = 0; x < 9; x++) { 
     for (int y = 0; y < 9; y++) { 
      if (pancakes[x] > pancakes[x + 1]) { 
       int valueSwitched = pancakes[x]; 
       pancakes[x] = pancakes[x + 1]; 
       pancakes[x + 1] = valueSwitched; 
      } 
     } 
    } 

    cout << "\n-----ListSorted-----\n\n"; 

    for (int x = 0; x < 10; x++) { 
     cout << "Person " << (x + 1) << " ate: " << pancakes[x] << endl; 
    } 

    return 0; 
} 

Answer 1

Ваш сортировочный код делает только то же самое, как

for (int x = 0; x < 9; x++) { 
    if (pancakes[x] > pancakes[x + 1]) { 
     int valueSwitched = pancakes[x]; 
     pancakes[x] = pancakes[x + 1]; 
     pancakes[x + 1] = valueSwitched; 
    } 
} 

принимая 9 раз больше.

Вам необходимо будет обменивать петли x и y.

for (int y = 0; y < 9; y++) 
{ 
    for (int x = 0; x < 9; x++) 
    { 
     if (pancakes[x] > pancakes[x + 1]) 
     { 
      int valueSwitched = pancakes[x]; 
      pancakes[x] = pancakes[x + 1]; 
      pancakes[x + 1] = valueSwitched; 
     } 
    } 
} 

Или более эффективно делать это, попробуйте следующее:

for (int y = 9; y > 0; y--) 
{ 
    for (int x = 0; x < y; x++) 
    { 
     if (pancakes[x] > pancakes[x + 1]) 
     { 
      int valueSwitched = pancakes[x]; 
      pancakes[x] = pancakes[x + 1]; 
      pancakes[x + 1] = valueSwitched; 
     } 
    } 
} 

Answer 2

Я нашел проблему только в sorting чисел. Поэтому вам нужно сначала изучить bubble sort. Я немного изменился в вашем коде. Так же см следующим образом:

for (int x = 0; x < 9; x++) { 
     for (int y = 0; y < 9-x; y++) {// changes 
      if (pancakes[y] > pancakes[y + 1]) {//changes 
       int valueSwitched = pancakes[y]; 
       pancakes[y] = pancakes[y + 1]; 
       pancakes[y + 1] = valueSwitched; 
      } 
     } 
    } 

теперь дают входы 9,8,7,6,5,4,3,2,1,0 и он работает ..

Answer 3

Во внутреннем цикле петли вы сравниваете и поменяв pancakes[x] и pancakes[x + 1] вместо сравнения и своп pancakes[y] и блины [y + 1].

for (int x = 0; x < 9; x++) { 
    for (int y = 0; y < 9; y++) { 
     if (pancakes[x] > pancakes[x + 1]) { 
      int valueSwitched = pancakes[x]; 
      pancakes[x] = pancakes[x + 1]; 
      pancakes[x + 1] = valueSwitched; 
     } 
    } 
} 

Я думаю, что это только опечатка.

Тем не менее я хотел бы указать, что использовать магические цифры как 9. Также существует традиция использовать имена i, j, k, l, m и n как индексы.

Что касается самого алгоритма, то его можно остановить, когда массив уже отсортирован.

Учтите, что вы можете использовать стандартную функцию std::swap для замены элементов массива.

Я покажу такой подход, когда циклы остановки итерации, когда массив уже отсортирован

#include <iostream> 

int main() 
{ 
    const size_t N = 10; 
    int pancakes[N]; 

    for (size_t i = 0; i < N; i++) 
    { 
     std::cout << "Please input the number of pancakes person " << i + 1 << " has eaten: "; 
     std::cin >> pancakes[i]; 
    } 

    size_t n = N; 
    while (!(n < 2)) 
    { 
     size_t last_sorted = 0; 
     for (size_t i = 1; i < n; i++) 
     { 
      if (pancakes[i-1] > pancakes[i]) 
      { 
       int valueSwitched = pancakes[i-1]; 
       pancakes[i-1] = pancakes[i]; 
       pancakes[i] = valueSwitched; 
       last_sorted = i; 
      } 
     } 

     n = last_sorted; 
    } 

    std::cout << "\n-----ListSorted-----\n\n"; 

    for (size_t i = 0; i < N; i++) 
    { 
     std::cout << "Person " << i + 1 << " ate: " << pancakes[i] << std::endl; 
    } 

    return 0; 
} 

Если ввести, например

10 1 9 2 8 3 7 4 6 5 

, то вы получите

Please input the number of pancakes person 1 has eaten: 10 
Please input the number of pancakes person 2 has eaten: 1 
Please input the number of pancakes person 3 has eaten: 9 
Please input the number of pancakes person 4 has eaten: 2 
Please input the number of pancakes person 5 has eaten: 8 
Please input the number of pancakes person 6 has eaten: 3 
Please input the number of pancakes person 7 has eaten: 7 
Please input the number of pancakes person 8 has eaten: 4 
Please input the number of pancakes person 9 has eaten: 6 
Please input the number of pancakes person 10 has eaten: 5 

-----ListSorted----- 

Person 1 ate: 1 
Person 2 ate: 2 
Person 3 ate: 3 
Person 4 ate: 4 
Person 5 ate: 5 
Person 6 ate: 6 
Person 7 ate: 7 
Person 8 ate: 8 
Person 9 ate: 9 
Person 10 ate: 10 

Если вы хотите сохранить связь между человеком и съеденными блинами человеком, тогда вы должны объявить массив пар.

Вот показательная программа

#include <iostream> 
#include <utility> 

int main() 
{ 
    const size_t N = 10; 
    std::pair<size_t, int> pancakes[N]; 

    for (size_t i = 0; i < N; i++) 
    { 
     std::cout << "Please input the number of pancakes person " << i + 1 << " has eaten.\n"; 
     pancakes[i].first = i + 1; 
     std::cin >> pancakes[i].second; 
    } 

    size_t n = N; 
    while (!(n < 2)) 
    { 
     size_t last_sorted = 0; 
     for (size_t i = 1; i < n; i++) 
     { 
      if (pancakes[i-1].second > pancakes[i].second) 
      { 
       auto valueSwitched = pancakes[i-1]; 
       pancakes[i-1] = pancakes[i]; 
       pancakes[i] = valueSwitched; 
       last_sorted = i; 
      } 
     } 

     n = last_sorted; 
    } 

    std::cout << "\n-----ListSorted-----\n\n"; 

    for (size_t i = 0; i < N; i++) 
    { 
     std::cout << "Person " << pancakes[i].first << " ate: " << pancakes[i].second << std::endl; 
    } 

    return 0; 
} 

Для того же входной сигнал, как описаны выше его отсортированный выход будет выглядеть

-----ListSorted----- 

Person 2 ate: 1 
Person 4 ate: 2 
Person 6 ate: 3 
Person 8 ate: 4 
Person 10 ate: 5 
Person 9 ate: 6 
Person 7 ate: 7 
Person 5 ate: 8 
Person 3 ate: 9 
Person 1 ate: 10