Основы программирования на С++ для начинающих

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

Алгоритм сортировки массива “пузырьковая сортировка” рассматривается практически во всех учебниках по программированию на С++. Его легко понять начинающим. Он наглядный и очень простой.

На практике этот алгоритм  почти никто не использует, так как он медлительный и есть более быстрые и усовершенствованные алгоритмы. Мы также разберем его потому, что сортировка “пузырьком” – это основа некоторых более эффективных алгоритмов, которые будут изложены в следующих статьях. Это  “быстрая” сортировка, “пирамидальная” сортировка и “шейкерная” сортировка.

Как работает “пузырьковая” сортировка? Допустим у нас есть неотсортированный  массив чисел из 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 ). В нем представлена “пузырьковая” сортировка в усовершенствованном варианте (когда отсортированные элементы массива уже не сравниваются между собой). Единственное – в наших примерах сравнение значений начиналось с последнего элемента.  А в предложенном видео –  от нулевого к последнему. Посмотрите и увидите, как элементы перемещаются в массиве на нужные места :)

9 thoughts on “Пузырьковая сортировка (сортировка “пузырьком”)

  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):

      c = a;
      a = b;
      b = c; // а и b поменялись значениями

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

      a, b = b, a

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

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

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

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

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

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

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

Добавить комментарий для Olej Отменить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *