Шейкерная сортировка на С++

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 4 нед., 1 день назад.

  • Автор
    Сообщения
  • #5401
    @admin

    Это второй алгоритм сортировки массивов, который будет выложен на сайте. Чтобы его изучить, пройдите сначала алгоритм сортировки пузырьком, так как данный алгоритм использует его основные идеи.

    Основная идея алгоритма шейкерной сортировки заключается в следующем: четные проходы делать от конца к началу, а нечетные — от начала к концу. Сложность этого алгоритма при выполнении в худшем случае будет $$n^2$$, как и у алгоритма сортировки пузырьком, но на практике он чуточку быстрее. Однако ни один из этих алгоритмов не пригоден для использования в реальной практике, они обучающие. Примерно так выглядит реализация данного алгоритма на C++:

    void ShakerSort(int *a, int n) {
        int left, right, i;
        left = 0;
        right= n - 1;
        while (left <= right) {
            for (i = right; i >= left; i--) {
                if (a[i-1] > a[i]) {
                    swap(a[i-1], a[i]);
                }
            }
            left++;
            for (i = left; i <= right; i++) {
                if (a[i-1] > a[i]) {
                    swap(a[i-1], a[i]);
                }
            }
            right--;
        }
    }

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

Для ответа в этой теме необходимо авторизоваться.