Пузырьковая сортировка (сортировка «пузырьком»)




пузырьковая сортировка с++, сортировка пузырьком с++, bubble sort c++

Алгоритм сортировки массива «пузырьковая сортировка» рассматривается практически во всех учебниках по программированию на С++. Его легко понять начинающим. Он наглядный и очень простой. На практике этот алгоритм почти никто не использует, так как он медлительный и есть более быстрые и усовершенствованные алгоритмы. Мы также разберем его потому, что сортировка «пузырьком» — это основа некоторых более эффективных алгоритмов, которые будут изложены в следующих статьях. Это «быстрая» сортировка, «пирамидальная» сортировка и «шейкерная» сортировка.

Как работает «пузырьковая» сортировка? Допустим у нас есть неотсортированный массив чисел из 5-ти элементов и нам предстоит разместить значения по возрастанию. Для наглядности, на рисунке изобразим этот массив вертикально «Исходный массив».

пузырьковая сортировка с++, сортировка пузырьком с++, bubble sort c++

Алгоритм сортировки «пузырьком» состоит в повторении проходов по массиву с помощью вложенных циклов. При каждом проходе по массиву сравниваются между собой пары «соседних» элементов. Если числа какой-то из сравниваемых пар расположены в неправильном порядке — происходит обмен (перезапись) значений ячеек массива. Образно говоря в нашем примере 2 «легче» чем 3 — поэтому обмен есть, далее 2 «легче» чем 7 — снова обмен и т.д. При сравнении нулевого и первого элемента на нашем рисунке обмена нет, так как 2 «тяжелее» чем 1. Таким образом более «легкое» значение, как пузырек в воде, поднимается вверх до нужной позиции. Вот почему у этого алгоритма такое название.

Рассмотрим алгоритм сортировки «пузырьком» в работе:

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

пузырьковая сортировка с++ для начинающих, сортировка пузырьком с++, bubble sort c++

Дополнить можно следующим: после того, как внутренний цикл отработает один раз, минимальное значение массива будет занимать нулевую ячейку. Поэтому при повторном проходе, очередное минимальное значение из оставшихся надо будет разместить в следующей ячейке (i + 1). Таким образом нет необходимости сравнивать между собой все элементы массива снова и количество обрабатываемых значений уменьшается на 1. При сортировке «пузырьком» необходимо пройти SIZE — 1 итераций внешнего цикла, так как сравнивать один элемент с самим собой — смысла нет.

Не будем забывать то, о чем мы говорили в самом начале — алгоритм «пузырьковой» сортировки малоэффективен и медлителен. Если у нас есть частично отсортированный массив и необходимо переместить в начало только одно значение, он все равно будет проходить все итерации циклов. То есть производить сравнение уже отсортированных значений массива, хотя этого уже можно и не делать.

Давайте немного улучшим эту ситуацию. Добавим в код еще одну переменную-«флажок», которая будет давать знать, произошел ли обмен значений на данной внешнего цикла итерации или нет. Перед тем, как войти во внутренний цикл, «флажок» будет сбрасываться в 0. Если обмен значениями в этом цикле случится — «флажку» будет присвоено значение 1, если нет — то он останется равным 0. В последнем случае (если «флажок» равен 0) — обменов не было и массив полностью отсортирован. Поэтому программе можно досрочно выйти из циклов, чтобы не тратить время попусту на последующие ненужные сравнения.

Рассмотрите следующий пример:

Видим такую картину после запуска:

пузырьковая сортировка с++ для начинающих, сортировка пузырьком с++, bubble sort c++

Видно что программа прошла вложенным циклом по массиву 1 раз, переместила значение 2 в нужное место и завершила работу. А вот, что будет на экране, если закомментировать все строки кода, где есть переменная-«флажок»:

пузырьковая сортировка с++ для начинающих, сортировка пузырьком с++, bubble sort c++

Программа вхолостую 4 раза «гоняла» по массиву, хотя значение 2 перемещено в нужную ячейку еще при первом проходе вложенным циклом.

В сети есть прикольное видео (автор: AlgoRythmics ). В нем представлена «пузырьковая» сортировка в усовершенствованном варианте (когда отсортированные элементы массива уже не сравниваются между собой). Единственное — в наших примерах сравнение значений начиналось с последнего элемента. А в предложенном видео — от нулевого к последнему. Посмотрите и увидите, как элементы перемещаются в массиве на нужные места :)

Рассылка новых уроков по программированию:

Дата
Страница
Пузырьковая сортировка на C++ для начинающих
Рейтинг
51star1star1star1star1star

Пузырьковая сортировка (сортировка «пузырьком»): 9 комментариев

  1. Добрый день.
    Помогите, пожалуйста разобраться в методе, ломаю голову не могу понять принцип двух вложенных циклов.
    Есть код:
    #include
    #include
    using namespace std;

    int main()
    {
    setlocale(LC_ALL, «Russian»);
    int nums[10];
    int a,b,t;
    int size;

    size = 10; // Количество сортируемых элементов.

    // Помещаем массив случайные числа.
    for(t=0; t<size; t++) nums[t] = rand();

    // Отображаем исходный массив.
    cout << "Исходный массив:\n ";
    for(t=0; t<size; t++) cout << nums[t] << ' ';
    cout << '\n';

    //Реализация алгоритма пузырьковой сортировки.
    for(a=1; a=a; b—) {
    if(nums[b-1] > nums[b]) { // Если значения элементов массива
    // расположены не по порядку,
    // то меняем их местами.
    t = nums[b-1];
    nums[b-1] = nums[b];
    nums[b] = t;
    }
    }

    // Отображаем отсортированный массив.
    cout << "\n Отсортированный массив:\n ";
    for(t=0; t<size; t++) cout << nums[t] << ' ';

    system("pause");
    return 0;
    }
    Интересует:
    for(a=1; a=a; b—) {
    if(nums[b-1] > nums[b]) { // Если значения элементов массива
    // расположены не по порядку,
    // то меняем их местами.
    t = nums[b-1];
    nums[b-1] = nums[b];
    nums[b] = t;
    }
    }
    Почему в цикле for(a=1; a<size; a++) a<siz а не a=a; b—) не могу разобрать.
    И последнее
    t = nums[b-1];
    nums[b-1] = nums[b];
    nums[b] = t;
    Можно ли как-нибудь упростить замену?

  2. Добрый день.
    Помогите, пожалуйста, разобраться в методе. Голову ломаю, не могу понять.
    Есть код с книжки:
    #include
    #include
    using namespace std;

    int main()
    {
    setlocale(LC_ALL, «Russian»);
    int nums[10];
    int a,b,t;
    int size;

    size = 10; // Количество сортируемых элементов.

    // Помещаем массив случайные числа.
    for(t=0; t<size; t++) nums[t] = rand()%100;

    // Отображаем исходный массив.
    cout << "Исходный массив:\n ";
    for(t=0; t<size; t++) cout << nums[t] << ' ';
    cout << '\n';

    //Реализация алгоритма пузырьковой сортировки.
    for(a=1; a=a; b—) {
    if(nums[b-1] > nums[b]) { // Если значения элементов массива
    // расположены не по порядку,
    // то меняем их местами.
    t = nums[b-1];
    nums[b-1] = nums[b];
    nums[b] = t;
    }
    }

    // Отображаем отсортированный массив.
    cout << "\n Отсортированный массив:\n ";
    for(t=0; t<size; t++) cout << nums[t] << ' ';

    system("pause");
    return 0;
    }
    Больше всего волнует вложенные циклы:
    for(a=1; a=a; b—)
    Во внешнем цикле почему a<size а не a=a что это такое и как оно работает?
    И последнее:
    Подскажите, как можно упросить перестановку:
    t = nums[b-1];
    nums[b-1] = nums[b];
    nums[b] = t;

    1. > Подскажите, как можно упростить перестановку:

      А что там упрощать?
      В C, C++ и подобным им языках (Pascal, Java и др.) обменять значения 2-х переменных (a и b) можно только чере 3-ю промежуточную переменную (c):

      В более высокоуровневых языках, таких как Python или Go, это можно было бы записать проще:

      1. Можно упростить с помощю ф-цыи swap() ;
        swap(arrForSort[j],arrForSort[j-1]);

      2. Можно записать через функцию swap() … только это вряд ли можно считать упрощением, потому что в этой функции делается то же самое.

      3. но как минимум не нужно вводить 3 переменную

      4. А в чём разница ? … от одной лишней переменной…
        Когда речь перейдёт от совершенно элементарных задач к более-менее обстоятельным, то один-два десятка переменных больше или меньше — перестают играть какую-то роль. Там вступают в игру другие критерии.

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

    Но соискатели на собеседованиях и студенты на экзаменах упортно «тулят» именно этот метод.
    В этом есть какая-то загадка…

    1. Да это привычка обычная. Метод самый простой для понимания, вот и тулят его везде.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>