Шейкер сортировка в C++: принцип работы

Всем привет! В прошлом статье мы изучили пузырьковую сортировку. Как мы уже узнали она не самый хороший выбор для сортировки. Но в прошлой статье мы также упомянули, что некоторые алгоритмы кое-что позаимствовали у пузырьковой сортировки (!) и из-за этого их начали называть ее разновидностями. Одна из таких разновидностей - шейкер сортировка.

Эта статья будет полезна тем кто еще делает первые шаги в программировании и тем кто просто хочет увеличить свой объем знаний об алгоритмах.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое шейкер сортировка

Мы можем сделать некоторые модификации в пузырьковой сортировке чтобы сделать ее быстрее.

Проблема пузырьковой сортировки заключается в том, что значения ячеек массива медленно занимают свои отсортированные позиции (индексы). И это нас наталкивает на способ ускорения алгоритма.

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

Такая разновидность пузырьковой сортировки называется - шейкер сортировка (Cocktail sort). У нее такое необычное название, потому что когда с помощью ее сортируют, массив похож на коктейль, который пытаются перемешать.

Как создать шейкер сортировку в C++

Ниже вы можете увидеть реализацию шейкер сортировки:

  bool sort_or_not = true;

  do {
    sort_or_not = true;
    for (int i = 0; i < n; i++) { // n - размер сортируемого массива
      if (chisla[i] > chisla[i + 1]) {
        swap (chisla[i], chisla[i + 1]);
        sort_or_not = false;
      }
    }
    for (int i = 4; i >= 1; i--) {
      if (chisla[i] < chisla[i - 1]) {
        swap (chisla[i], chisla[i - 1]);
        sort_or_not = false;
      }
    }
  } while (sort_or_not == false);

Давайте разберем как этот код работает:

С помощью булевой переменной sort_or_not, которую мы создали в первой строчке и сразу же присвоили значение true, мы будем узнавать меняли ли ячейки свое значение (за два цикла):

• sort_or_not принимает значение false, если результаты условий, которые находятся в строках 6 и 12 равны true.

Весь смысл заключается в том, что в условии цикла do while написано (пока) sort_or_not == false. Это значит пока меняются значения ячеек между собой, мы заканчивать сортировку не собираемся.

Если же булева переменная sort_or_not за цикл не стала равна false, то мы спокойно выходим из цикла.

Внутри цикла do while вы можете увидеть две поочередно стоящие алгоритмы пузырьковой сортировки, только с разными направлениями сортировки (мы это упомянули выше).

Как видите реализация не такая уж и сложная, как могла показаться в начале. Также этот алгоритм можно сделать быстрее, но об этом ниже.

Как можно улучшить шейкер сортировку

Вы наверно уже заметили, что самый большой элемент перемещается в конец массива (за первый цикл в do while), а самый маленький элемент переместится вниз на одну ячейку.

В следующем цикле все уже произойдет наоборот: самый маленький элемент переместится в начала массива, а второй по размерам элемент переместится на одну ячейку вверх. Так же будет для оставшихся элементов.

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

• Поэтому ниже в строке 2: мы создали переменную right, в ней будет находиться правая граница массива
• А в строке 3: создали переменную left, в которой будет храниться начала массива.

Переменную right мы будем уменьшать на один после первого цикла for (который находится в строках 6 - 11), left же будем уменьшать после второго цикла (ну или другими словами в самом конце цикла do while).

Так мы сможем ускорить алгоритм в несколько раз (все зависит от размера массива).

Ниже, находится оптимизированная версия шейкер сортировки:

  bool sort_or_not = true;
  int right = n - 1; // n - размер массива
  int left = 1;
  do {
    bool sort_or_not = true;
    for (int i = left; i <= right; i++) {
      if (chisla[i - 1] > chisla[i]) {
        swap (chisla[i - 1], chisla[i]);
        sort_or_not = false;
      }
    }
    right--;
    for (int i = right; i >= left; i--) {
      if (chisla[i] < chisla[i - 1]) {
        swap (chisla[i], chisla[i - 1]);
        sort_or_not = false;
      }
    }
    left++;
 } while (sort_or_not == false);

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Использовать ли шейкер сортировку

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

Дело в том, что скорость шейкер сортировки отличается (но не на много) от сортировки пузырьком. Все потому что сумма сравнений одинакова с пузырьковой сортировкой, а вот сумма обменов меньше чем у нее.

Конечно шейкер сортировка лучше пузырьковой сортировки, но по сравнению с другими алгоритмами она отстает и даже намного (!).

• Плюс один, как и у многих простеньких алгоритмов - простая реализация.
• Минус один - медленная работа алгоритма.

Если вы знаете только пузырьковую и шейкер сортировку, то лучше используйте последнюю сортировку. Так вы хоть не намного, но увеличите скорость вашей программы.

Упражнение

Закрепите шейкер сортировку на практике создав массив на 5 ячеек и заполнив его любыми своими числами, и конечно отсортируйте его с помощью сортировки, которую мы сегодня прошли. Надеемся вы знаете, о какой сортировке идет речь=)

Мы рады, если вы нашли в этой статье то что и искали. Если у вас есть какие-то вопросы по этой теме или же заметили ошибку в этой статье, то пишите ниже в комментарии. Удачи!

« Стек в C++

Пузырьковая сортировка в C++ »