Зачем пузырьковой сортировке нужны вложенные циклы?

Я собираюсь начать новый вопрос. Я задал вопрос вчера и хотел знать, в чем проблема в моей программе. Программа приведена ниже, и вы, люди, указали, что эта следующая программа выполняет только один проход сортировки и также нуждается во внешнем цикле. В то время я был хорош, как хорошо. Но снова, когда я посмотрел программу, я запутался, и мне нужно спросить, зачем нам нужен внешний цикл для сортировки, поскольку только один цикл может выполнять сортировку (на мой взгляд). Сначала посмотрите программу ниже, затем я представлю свою логику в конце программы.

#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]. Тогда почему этого не происходит и цикл завершается только после прохода? Другими словами, может быть, я пытаюсь спросить, ЕСЛИ оператор не повторяется в цикле for? На мой взгляд, это так. Я очень благодарен за помощь и мнения, мой вопрос может быть небольшого уровня, но именно так я буду прогрессировать.


person Hammad    schedule 04.09.2012    source источник
comment
Это очень простой вопрос о сортировке, я дам вам подсказку: поместите наименьшее значение в последнюю позицию [9]. Он будет сравнен и перемещен на предыдущую позицию [8], после чего ваш цикл завершится. Просто сортировка еще не закончена.   -  person Argeman    schedule 04.09.2012
comment
Очень простой и понятный пример. Спасибо   -  person Hammad    schedule 04.09.2012


Ответы (4)


Позвольте мне привести пример, возьмем только 3 числа. Итак, вы вводите

13, 3 ,1 

Теперь вы начинаете сортировать, как вы это сделали. поэтому он сравнивает 13 и 3 13 > 3, поэтому поменяйте их оба. теперь у нас есть.

3, 13, 1

Теперь он будет сравнивать, как вы сказали, следующая пара = 13 и 1 13 > 1, поэтому новый порядок будет

3, 1, 13

теперь ваш цикл завершен, и вы пропустили сравнение 3 и 1. На самом деле первый цикл сортирует только наибольшее число!

person lorenz albert    schedule 04.09.2012
comment
Я не знаю, где это сделать, так как я новичок на этом сайте. Неважно, я делаю это, посмотрев, где это можно сделать. - person Hammad; 04.09.2012
comment
@ user1643568: Как спрашивающий, вы имеете право принять ответ. Вы можете сделать это, нажав на зеленую галочку (V) рядом с одним из ответов. Вы можете принять только один ответ, и это должен быть ответ, который ВАМ больше всего помог. - person amit; 04.09.2012
comment
Слева от моего поста есть контур галочки. Нажатие на нее означает, что вы принимаете этот пост как лучший - person lorenz albert; 04.09.2012
comment
Трудно выбрать между ответом Амита и Лоренца Альберта. Оба были идеальными, но, поскольку Лоренц спросил об этом, я отметил его ответ как лучший. Амит также был ясным и всеобъемлющим. - person Hammad; 04.09.2012

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

Это неправильно. Не вдаваясь в подробности, постоянного количества циклов недостаточно для сортировки, поскольку сортировка — это 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) алгоритмы, основанные на сравнении, если быть точным.

person amit    schedule 04.09.2012
comment
Спасибо, амит. Означает, что в одном цикле одно число находится в правильном положении. Повторение n (где n = элементы для сортировки) отсортирует все n чисел. Спасибо, это помогло мне устранить двусмысленность. - person Hammad; 04.09.2012
comment
@user1643568: Точно. Вот что делает пузырьковая сортировка. Это также то, как мы можем доказать, что это (сортировка пузырьком) работает. Я рад, что помог вам лучше понять, как это работает. - person amit; 04.09.2012
comment
Хотя ответ, выбранный как лучший, также дал правильный ответ, но вы объяснили его более качественно и подробно. Спасибо. - person Sambhav Pandey; 01.09.2016

Для пузырьковой сортировки проход просто перемещает самый большой элемент в конец массива. Итак, вам нужно пройти 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 самый большой элемент перемещается в конец массива

person Ankur    schedule 04.09.2012

Это неправильно, потому что

Алгоритм получил свое название из-за того, что элементы меньшего размера всплывают вверх списка. (пузырьковая сортировка)

Итак, в конце первого цикла мы получаем наименьший элемент. Итак, для полной сортировки нам нужно сохранить всего n циклов. (где n = общий размер чисел)

person Manan Shah    schedule 04.09.2012