Шейкер-сортировка

Шейкер-сортировка представляет собой дальнейшую и довольно качественную оптимизацию пузырьковой сортировки(без знания которой данная задача останется непонятной).

Представим себе еще раз пузырьковую сортировку. При сортировке по возрастанию и направлении прохода по последовательности слева направо - большие числа занимают свои надлежащие места очень быстро: либо уже в пределах этого подхода, либо в нескольких следующих.

Например, имеем: [7,3,4,6] - после первого прохода получим уже [3,4,6,7] - т.о. 7 пройдя через весь массив встало на свое место уже на первом проходе. Другое дело - маленькие числа в данной ситуации: на каждой итерации они продвигаются к своему месту не больее чем на 1 позицию: [7,6,5,2,1] - после 1-ой итерации имеем [6,5,2,1,7], после 2-ой - [5,2,1,6,7] и т.д.

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

С учетом всего вышесказанного получим:

left  = 1
right = n-1
 
last  = n-1
 
/* основной цикл до тех пор пока границы
       отсортированных с разных сторон отрезков
       не пересекутся */
while left < right
    /* проход снизу вверх */
    for j = right downto 1
        if x[j-1] > x[j]
            swap(x, j-1, j)
            last = j
 
    /* Корректируем нижнюю границу
       до которой уже все элементы получились
       отсортироваными */
    left = last + 1
 
    /* проход сверху вниз */
    for j = 1 to right
        if (x[j-1] > x[j] )
            swap(x, j-1, j)
            last = j
 
    /* Корректируем верхнюю границу
       после которой уже все элементы получились
       отсортироваными */
    right = last - 1
 

Данный сортировка работает быстрее чем пузырьковая, но по-прежнему производительность алгоритма в среднем ~ O(n²), а число обменов вообще не поменялось даже по-сравнению базовой реализацией пузырькового метода. Всеми этими манипуляциями с оптимизацией мы сократили только количество сравнений.

Из преимуществ можно отметить быструю(сравнимую с другими истинно быстрыми алгоритмами) сортировку частично упорядоченного массива.

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 Шейкер сортировка ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void ShakerSort(T* x) {
    int last = n-1;
    int left = 1, right = n-1;
 
    /* основной цикл до тех пор пока границы
       отсортированных с разных сторон отрезков
       не пересекутся */
    do {
        /* проход снизу вверх */
        for (int j = right; j > 0; j--) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
 
        /* Корректируем нижнюю границу
           до которой уже все элементы получились
           отсортироваными */
        left = last + 1;
 
        /* проход сверху вниз */
        for (int j = 1; j <= right; j++) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
 
        /* Корректируем верхнюю границу
           после которой уже все элементы получились
           отсортироваными */
        right = last - 1;
    } while (left < right);
}

template<class T> void swap(T* x, int i, int j) { T tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp; } template<class T> void ShakerSort(T* x) { int last = n-1; int left = 1, right = n-1; /* основной цикл до тех пор пока границы отсортированных с разных сторон отрезков не пересекутся */ do { /* проход снизу вверх */ for (int j = right; j > 0; j--) { if (x[j-1] > x[j]) { swap(x, j-1, j); last = j; } } /* Корректируем нижнюю границу до которой уже все элементы получились отсортироваными */ left = last + 1; /* проход сверху вниз */ for (int j = 1; j <= right; j++) { if (x[j-1] > x[j]) { swap(x, j-1, j); last = j; } } /* Корректируем верхнюю границу после которой уже все элементы получились отсортироваными */ right = last - 1; } while (left < right); }

Является окончательной оптимизацией пузырькового подхода сортировки.
Но в целом, алгоритм один из самых медленных.

Производительность: ~ O(n²)
Расход памяти: - (только на счетчики цикла, доп. переменные и проч.)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0