Сортировка данных в массиве
От: Аноним optim.ru  
Дата: 13.06.03 03:15
Оценка: 390 (7)
Статья :
Сортировка данных в массиве
Автор(ы):
В этом разделе будет рассмотрен знаменитый алгоритм ''быстрой'' сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов — сортировку вставками.


Авторы :
optim.ru
Re: Сортировка данных в массиве
От: Dmi_3 Россия  
Дата: 25.12.05 14:25
Оценка: 2 (1)
>Сортировка данных в массиве
Автор(ы):
В этом разделе будет рассмотрен знаменитый алгоритм ''быстрой'' сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов — сортировку вставками.

>Дискуссия
Автор: AndrewVK
Дата: 08.05.05


Уважаемые коллеги. К сожалению, я только сейчас наткнулся на эту ветку. Т.к. здесь собрались знающие люди, прошу помощи. Есть нижеприведённый (тестовый) алгоритм сортировки. Время его работы и количество сравнений и обменов (в тестовых примерах) очень радуют. Иногда (даже без вырождения) он в три раза быстрее std::sort из MSVC 7.1.
Не могли бы вы высказать своё мнение об этом алгоритме (не о коде, а именно об алгоритме). Особенно интересуют доказательство правильности алгоритма и построение вырожденного случая или доказательство его отсутствия, (классики утверждают, что он есть всегда).
Для стандартной медианы из трёх вырожденный случай это циклически сдвинутый на один элемент отсортированный массив. Уж больно легко его получить, а потом обвинить автора алгоритма в собственной неграмотности. Поэтому я использую "золотую" медиану.

Модифицированная сортировка Хоара (QuickSort) с улучшенными разбиением и завершением.
На вход сортировке должен подаваться полуоткрытый интервал (включая начало исключая конец)
Алгоритм параметризован типом итератора и процедурой сравнения.
Для обменов используется std::iter_swap. Почему-то никто не параметризует алгоритм сортировки алгоритмом обмена. Видимо считается, что надо писать свой итератор и специализировать std::iter_swap для специфических обменов.

От итератора (указателя на данные) требуются ТОЛЬКО:
~Iterator ( ) ; //Деструктор. O(1)
Iterator (Iterator const&) ; //Конструктор копий. O(1)
Iterator& opertor= (Iterator const&) ; //Присваивание. O(1)
Iterator operator+ (distance )const; //Сдвиг итератора. O(1)
distance operator- (Iterator const&)const; //Получение дистанции. O(1)
distance должен быть очень похож на int
Все перечисленные операции должны выполняться за O(1), не вызывать исключений при работе внутри подаваемого интервала и не запускать ядерных ракет... При этом сортировка выполняется за O(N*Ln(N)) где N-количество сортируемых данных.
От самих сортируемых данных напрямую не требуется ничего. Косвенно (через итератор), элементы должны уметь сравниваться и обмениваться местами. Это кардинально отличает алгоритм от многих других и теоретически может позволить сортировать некоторые данные не влезающие в память.

Усовершенствования разбиения:
1) В качестве разделителя выбирается медиана из значений первого, последнего и "золотого"-среднего элементов.
2) При нахождени медианы эти элементы сортируются и располагаются в следующем порядке
{ начало:маленький, начало+1:средний(разделитель-медиана), конец:большой }.
Это ДО ПРЕДЕЛА упрощает (ускоряет) внутренние циклы процедуры "деление",
способствует разбиению на равные части (что уменьшает итоговое число сравнений)
и практически исключает вырождение метода.
На практике нужный размер стека возрастает 1.618 — 2.618 раза оставаясь O(ln(N)).
3) По окончании разбиения медиана переносится в позицию разделяющую меньшие и большие элементы и в случае если все элементы различны уже не участвует в дальнейших разбиениях.(это тоже дает небольшой выигрыш особенно в коротких интервалах)

Усовершенствования завершения:
Сортировка Хоара (QuickSort) эффективна только для больших интервалов, а в процессе её работы возникают множества из малого числа элементов. Их лучше сортировать другими методами. Обычно для этого применяют сортировку вставками, но для каждого конкретного количества элементов существует семейство лучших алгоритмов (в смысле числа сравнений \ обменов). Они и применены для завершения. (минимизируют только максимальное а не среднее число сравнений).

template<class Iterator,int(*const Cmp)(Iterator,Iterator)>
void _hoar_sort(Iterator begin,int size/*,int limit=100*/) throw()
{
    for(--size;;){
        switch(size){//Сортировка маленьких интервалов.
#define step(x,y) if(Cmp(begin+x,begin+y))std::iter_swap(begin+x,begin+y)
            case 4: step(1,0);step(3,2);step(3,1);step(4,3);
            case 3: step(1,0);step(3,2);step(3,1);
            case 2: step(2,0);step(2,1);else
            case 1: step(1,0);
            case 0: return;
#undef step
        };
        //Заглушка на невероятный случай вырождения.
        //if(0==--limit){tree_sort<Iterator,Cmp>(begin,size+1);return;}
        Iterator low_bound(begin),high_bound(begin+size);//Закрытый интервал
        //Предсортировка и выбор Фибоначчи-медианы.
        if(Cmp(high_bound,low_bound))
            std::iter_swap(low_bound,high_bound);
        low_bound=low_bound+1;
        //Обмен примерно с Фибоначчи-средним элементом
        std::iter_swap(low_bound+size*3/8,low_bound);
        if(Cmp(high_bound,low_bound))
            std::iter_swap(low_bound,high_bound);
        else if(Cmp(low_bound,begin))
            std::iter_swap(begin,low_bound);
        //Разбиение.
        for(Iterator const separator(low_bound);;)
        {
            while(Cmp(low_bound=low_bound+1,separator));
            while(Cmp(separator,high_bound=high_bound-1));
            if(0<high_bound-low_bound){
                std::iter_swap(low_bound,high_bound);
            }else{
                std::iter_swap(separator,high_bound);
                break;
            }
        }
        _hoar_sort<Iterator,Cmp>(begin,high_bound-begin/*,limit*/);
        size-=low_bound-begin;
        begin=low_bound;
    }
}


P.S.
Анализ недостатков RSDN QuickSort
template <class T>
void QuickSort(T A[], int low, int high)
{
    // локальные переменные, содержащие индекс середины - mid,
    // центральный элемент и индексы сканирования
    T pivot;//NOTE: Мой конструктор T::T() запускает ядерные ракеты!
    int scanUp, scanDown;
    int mid;

    // если диапазон индексов не включает в себя
    // как минимум два элемента, завершить работу
    if(high - low <= 0)
        return;
    else if(high - low == 1)
    {
        // если в подсписке два элемента, сравнить их между собой
        // и поменять местами при необходимости
        if(A[high] < A[low])
            Swap(A[low], A[high]);
        return;
    }

    // Рассчитать индекс середины и поместить значение соответствующего 
    // элемента массива в переменную pivot.
    //NOTE: Слишком легко получить вырождение.
mid = (low + high)/2;
    //NOTE: Мой T::operator=() тоже запускает ядерные ракеты!!!
    pivot = A[mid];

    // Поменять местами центральный и начальный элементы списка.
    Swap(A[mid], A[low]);
    // Инициализировать индексы scanUp и scanDown.
    scanUp = low + 1;
    scanDown = high;

    // Искать элементы, расположенные не в тех подсписках.
    // Остановиться при scanDown < scanUp.
    do
    {
        // Продвигаться вверх по первому подсписку. Остановиться,
        // когда scanUp укажет на второй подсписок или если
        // указываемый этим индексом элемент > центрального.
        //NOTE: Не эффективно. Два сравнения на итерацию.
        //NOTE: У меня нет T::operator<=
        while(scanUp <= scanDown && A[scanUp] <= pivot)
            scanUp++;

        // Продвигаться вниз по второму подсписку. Остановиться,
        // когда scanDown указжет на элемент >= центральному.
        //NOTE: У меня нет T::operator>
        while(A[scanDown] > pivot)
            scanDown--;

        // Если индексы все еще в своих подсписках, то они указывают
        // на два элемента, находящихся не в тех подсписках.
        if(scanUp < scanDown)
        {
            // Поменять их местами
            Swap(A[scanUp], A[scanDown]);
        }
    }
    while(scanUp < scanDown);

    // Скопировать элемент на который указывает точка разбиения
    // в первый элемент первого подсписка, ...
    A[low] = A[scanDown];//NOTE: Опять ядерные ракеты!
    // а центральный элемент в точку разбиения
    A[scanDown] = pivot;//NOTE: Опять ядерные ракеты!

    // если первый подсписок (low...scanDown-1) имеет 2 или более
    // элемента, выполнить для него рекурсивный вызов QuickSort
    if(low < scanDown-1)
        QuickSort(A, low, scanDown-1);

    // если второй подсписок (scanDown+1...high) имеет 2 или более
    // элемента, выполнить для него рекурсивный вызов QuickSort
    if(scanDown+1 < high)
        QuickSort(A, scanDown+1, high);
}

Алгоритм конечно гораздо лучше чем MSVC 6.0 std::sort но критики не выдерживает.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.