Зачем Bubble Sort нужны вложенные циклы?
Я собираюсь начать новый вопрос. Я задал вопрос вчера и хотел знать, в чем проблема в моей программе. Программа приведена ниже, и вы, люди, отметили, что эта следующая программа выполняет только один проход сортировки и также нуждается во внешнем цикле. В то время я был хорош, как хорошо. Но опять же, когда я посмотрел программу, я запутался и должен был спросить, зачем нам нужен внешний цикл для сортировки, поскольку только один цикл может выполнить сортировку (по моему мнению). Сначала посмотрите программу ниже, затем я представлю свою логику в конце программы.
#include <iostream.h>
#include <conio.h>
using namespace std;
main()
{
int number[10];
int temp = 0;
int i = 0;
cout << "Please enter any ten numbers to sort one by one: "<< "\n";
for (i = 0; i < 10; i++)
{
cin >> number[i];
}
i = 0;
for (i = 0; i < 9; i++)
{
if (number[i] > number[i + 1])
{
temp = number[i + 1];
number[i + 1] = number[i];
number[i] = temp;
}
}
i = 0;
cout << "The sorted numbers are given below:"<< "\n";
for (i = 0; i < 10; i++)
{
cout << number[i] << "\n";
}
getch();
}
Я думаю, что ТОЛЬКО цикл с пузырьковым условием должен выполнить сортировку. Посмотрите на следующий цикл программы:
for (i=0;i<9;i++)
if(number[i]>number[i+1])
{
temp=number[i+1];
number[i+1]=number[i];
number[i]=temp;
}
Теперь я объясню, что я думаю о том, что должен делать этот цикл. Сначала он сравнит число [0] с числом [1]. Если условие выполнено, он будет делать то, что находится в теле оператора IF. Тогда я буду увеличиваться на 1 (i ++). Тогда на следующей итерации сравниваемые значения будут числом [1] с числом [2]. Тогда почему этого не происходит и цикл выходит только после прохода? Другими словами, может быть, я пытаюсь попросить, чтобы оператор IF не повторялся в цикле for? На мой взгляд, это так. Я очень благодарен за помощь и взгляды, мой вопрос может быть небольшого уровня, но именно так я буду прогрессировать.
Решение
Позвольте мне привести пример, давайте возьмем только 3 числа. Таким образом, вы вводите
13, 3 ,1
Теперь вы начинаете сортировать, как вы это сделали. так что сравнивает 13 и 3
13 > 3 так что поменяйте их обоих
теперь у нас есть.
3, 13, 1
Теперь это будет сравнивать, как вы сказали, следующая пара = 13 и 1
13 > 1 поэтому новый порядок будет
3, 1, 13
Теперь ваш цикл закончен, и вы пропустили сравнение 3 и 1
На самом деле первый цикл сортирует только наибольшее число!
Другие решения
поскольку только один цикл может сделать сортировку (по моему мнению)
Это не правильно. Не вдаваясь в детали, постоянное количество циклов недостаточно для сортировки, так как сортировка Omega(nlogn) проблема. Значение, O(1) (константа, в том числе 1) количества циклов ему недостаточно — для любого алгоритма1,2.
Рассмотрим вход
5, 4, 3, 2, 1
одна петля пузырьковой сортировки будет делать:
4, 5, 3, 2, 1
4, 3, 5, 2, 1
4, 3, 2, 5, 1
4, 3, 2, 1, 5
Таким образом, алгоритм получит массив: [ 4, 3, 2, 1, 5], который не отсортирован.
После одна петля пузырьковой сортировки, у вас гарантированно будет только последний элемент на месте (что действительно происходит в примере). Вторая итерация убедится, что 2 последних элемента на месте, а nЭта итерация убедится, что массив действительно отсортирован, в результате чего n циклы, что достигается с помощью вложенного цикла.
(1) Внешний цикл иногда скрывается как рекурсивный вызов (быстрая сортировка это пример, где это происходит) — но есть еще цикл.
(2) Алгоритмы на основе сравнений, если быть точным.
Для пузырьковой сортировки проход просто перемещает самый большой элемент в конец массива. Так что вам нужно n-1 проходов, чтобы получить отсортированный массив, поэтому вам нужен другой цикл. Теперь для вашего кода значит 1 балл
if(number[0]>number[0+1])
{
temp=number[0+1];
number[0+1]=number[0];
number[0]=temp;
}
if(number[1]>number[1+1])
{
temp=number[1+1];
number[1+1]=number[1];
number[1]=temp;
}
.....6 more times
if(number[8]>number[8+1])
{
temp=number[8+1];
number[8+1]=number[8];
number[8]=temp;
}
так как вы можете видеть, что оператор IF повторяется, просто после всех 9 IF элемент largets перемещается в конец массива
Это не правильно, потому что
Алгоритм получил свое название от способа меньшие элементы «пузырь» на вершину списка. (Пузырьковая сортировка)
Итак, в конце первого цикла мы получаем самый маленький элемент. Итак, для полной сортировки мы должны сохранить всего n петель. (где n = общий размер чисел)