adaptive sort
От: alexeiz  
Дата: 06.01.06 10:25
Оценка:
Какой на сегодняшний день наиболее оптимальный алгоритм сортировки? Массивы в памяти. Время сравнения и обмена — одного порядка. Интересует алгоритм, который ко всему прочему сортирует почти отсортированные последовательности за время меньшее чем n*log(n).

Вообщем, что у меня есть на настоящий момент: quicksort с 3-way partitioning и random pivot + insertion sort для короткий подпоследовательностей. Работает неплохо. Random pivot вроде бы даёт некоторую adaptiveness, но мне кажется, что есть более эффективные алгоритмы. Вопрос какие?
Re: adaptive sort
От: minorlogic Украина  
Дата: 06.01.06 11:13
Оценка:
Merge sort , который учитывает монотонность последовательности. Отсортированный и обратно отсортированный за O(n)
Ищу работу, 3D, SLAM, computer graphics/vision.
Re: adaptive sort
От: _DAle_ Беларусь  
Дата: 06.01.06 11:26
Оценка: 4 (1)
Здравствуйте, alexeiz, Вы писали:

A>Какой на сегодняшний день наиболее оптимальный алгоритм сортировки? Массивы в памяти. Время сравнения и обмена — одного порядка. Интересует алгоритм, который ко всему прочему сортирует почти отсортированные последовательности за время меньшее чем n*log(n).


A>Вообщем, что у меня есть на настоящий момент: quicksort с 3-way partitioning и random pivot + insertion sort для короткий подпоследовательностей. Работает неплохо. Random pivot вроде бы даёт некоторую adaptiveness, но мне кажется, что есть более эффективные алгоритмы. Вопрос какие?


Если волнует сложность в худшем случае, то есть introsort (тот же quicksort + insertion sort, только еще плюс переход на heapsort при достижении некоторой глубины рекурсии). Сложность в худшем случае O(nlogn).
Насчет почти отсортированный последовательностей, есть smoothsort, но быстрым в среднем он вряд ли будет.
Re[2]: adaptive sort
От: alexeiz  
Дата: 06.01.06 11:26
Оценка:
Здравствуйте, minorlogic, Вы писали:

M> Merge sort , который учитывает монотонность последовательности. Отсортированный и обратно отсортированный за O(n)


Merge sort медленнее quick sort'а на случайных последовательностях. Мне бы и то и другое желательно. Можно, как-либо узнать относительную отсортированность последовательности перед сортировкой, чтобы выбрать соответствующий алгоритм?
Re[2]: adaptive sort
От: alexeiz  
Дата: 06.01.06 11:34
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Если волнует сложность в худшем случае, то есть introsort (тот же quicksort + insertion sort, только еще плюс переход на heapsort при достижении некоторой глубины рекурсии). Сложность в худшем случае O(nlogn).


Я такое видел в Dinkumware библиотеке. Интересно, когда (на каких последовательностях) происходит это достижение большой глубины рекурсии в quick sort'е? Вроде бы соответствующим выбором pivot можно достичь худшего случая nlogn, или я не прав? Настолько ли часто встречаются такие последовательности, что применение heapsort'а необходимо?

_DA>Насчет почти отсортированный последовательностей, есть smoothsort, но быстрым в среднем он вряд ли будет.
Re[3]: adaptive sort
От: _DAle_ Беларусь  
Дата: 06.01.06 15:36
Оценка:
Здравствуйте, alexeiz, Вы писали:

A>Здравствуйте, _DAle_, Вы писали:


_DA>>Если волнует сложность в худшем случае, то есть introsort (тот же quicksort + insertion sort, только еще плюс переход на heapsort при достижении некоторой глубины рекурсии). Сложность в худшем случае O(nlogn).


A>Я такое видел в Dinkumware библиотеке. Интересно, когда (на каких последовательностях) происходит это достижение большой глубины рекурсии в quick sort'е? Вроде бы соответствующим выбором pivot можно достичь худшего случая nlogn, или я не прав? Настолько ли часто встречаются такие последовательности, что применение heapsort'а необходимо?


Если используется random pivot, то не зная как работает генератор, подобрать последовательность, на которой данная реализация quicksort гарантированно выполнит порядка n^2 сравнений, очевидно невозможно. Вероятность такого события тоже достаточно мала. Если же генератор случайных чисел известен, то построить такую последовательность труда не представляет.

Тут скорее возникает другой вопрос, насколько быстро происходит выбор pivot'a? Если заменить random pivot на, например, медиану первого, последнего и среднего элементов, как изменится производительность сортировки?
Re[3]: adaptive sort
От: minorlogic Украина  
Дата: 06.01.06 16:25
Оценка:
Здравствуйте, alexeiz, Вы писали:

A>Здравствуйте, minorlogic, Вы писали:


M>> Merge sort , который учитывает монотонность последовательности. Отсортированный и обратно отсортированный за O(n)


A>Merge sort медленнее quick sort'а на случайных последовательностях. Мне бы и то и другое желательно. Можно, как-либо узнать относительную отсортированность последовательности перед сортировкой, чтобы выбрать соответствующий алгоритм?


Неа , не слышал , о подобной реализации , но может самому придумать ? типа пройтись по элементам и подсчитать к-во монотонных участков ?
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[4]: adaptive sort
От: Dmi_3 Россия  
Дата: 06.01.06 22:39
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Если же генератор случайных чисел известен, то построить такую последовательность труда не представляет.


ВАУ! Помоги плиз. Вот я незнаю как вырождающий пример здесь
Автор: Dmi_3
Дата: 25.12.05
построить.
Re[5]: adaptive sort
От: _DAle_ Беларусь  
Дата: 07.01.06 16:53
Оценка: 4 (1)
Здравствуйте, Dmi_3, Вы писали:

D_>Здравствуйте, _DAle_, Вы писали:


_DA>>Если же генератор случайных чисел известен, то построить такую последовательность труда не представляет.


D_>ВАУ! Помоги плиз. Вот я незнаю как вырождающий пример здесь
Автор: Dmi_3
Дата: 25.12.05
построить.


Ну я не утверждал что мне труда не представляет , ну раз уж сказал..
Здесь файлик, в нем последовательность из всего 20000 интов, если скормить на вход твоей сортировке, думает относительно долго. Если раскомментарить limit, то можно заметить, что глубина достигает чего-то около 10000.

Строил просто, на каждой итерации делаем так, чтобы медианный элемент был на самом деле вторым по возрастанию из всего интервала. Для этого, берем массив начальных позиций, то есть массив интов от 0 до size-1, затем моделируем обмены при поиске медианы, и расставляем в результирующем массиве числа по возрастанию в нужные позиции.

    const int len = 20000;
    vector<int> v(len); // массив позиций
    vector<int> a(len,0); // результирующая последовательность
    for (int i = 0; i < len; ++i)
        v[i] = i;
    int begin = 0;
    int cnt = 1;
    for (int j = 0; j < len/2-3; ++j)
    {
        int median = begin+1+(len-begin-1)*3/8;
        a[v[begin]] = cnt++;     // минимальное число в неотсортированной части
        a[v[median]] = cnt++;
        swap(v[begin+1], v[median]);
        begin += 2; // на каждой итерации "теряем" только два числа
    }
    for (int k = 0; k < len; ++k)
    {
        if (a[k] == 0) a[k] = len + 10; 
    }
Re[6]: adaptive sort
От: Dmi_3 Россия  
Дата: 08.01.06 11:11
Оценка:
Здравствуйте, _DAle_, Вы писали:

D_>>ВАУ! Помоги плиз. Вот я незнаю как вырождающий пример здесь
Автор: Dmi_3
Дата: 25.12.05
построить.


_DA>Ну я не утверждал что мне труда не представляет , ну раз уж сказал..

_DA>Здесь файлик, в нем последовательность из всего 20000 интов, если скормить на вход твоей сортировке, думает относительно долго. Если раскомментарить limit, то можно заметить, что глубина достигает чего-то около 10000.

Спасибо. Правда сначала долго не мог понять почему не вырождается. У меня limit был раскомментирован. В своё оправдание замечу что такую вырождающую последовательность на практике довольно трудно получить в отличии от RSDN::sort которая вырождается уже просто на одинаковых значениях в массиве и на частично реверсированных отсортированных массивах.

_DA>Строил просто, на каждой итерации делаем так, чтобы медианный элемент был на самом деле вторым по возрастанию из всего интервала.


Я протормозил. Пытался сделать так чтобы только один элемент за итерацию отбрасывался. Сейчас доказал что это невозможно. Для тех кто захочет проверить код привожу используемую в нём tree_sort. Она тоже оперирует только сравнениями и обменами. К сожалению из-за этого ана отстаёт по производительности от std::make_heap + std::sort_heap. Но я считаю, что это разумная плата за возможность более широкого использования и гарантию отсутствия "побочных" эффектов.

template<class Iterator,int(*const Cmp)(Iterator,Iterator)>
void _fix(Iterator begin,int size,int idx){
    SORT_ASSERT(idx<size);
#define   LEFT(X) ((X)*2+1)
#define  RIGHT(X) ((X)*2+2)
#define PARENT(X) ((X-1)/2)
    for(int Index(idx);;){
        int const l( LEFT(Index));
        int const r(RIGHT(Index));
        int tmp=(l<size&&Cmp(begin+Index,begin+l)) ? l : Index;
        if(r<size&&Cmp(begin+tmp,begin+r))
            tmp=r;
        if(tmp==Index)
            break;
        std::iter_swap(begin+Index,begin+tmp);
        Index=tmp;
    }
#undef LEFT
#undef RIGHT
#undef PARENT
}

template<class Iterator,int(*const Cmp)(Iterator,Iterator)>
void tree_sort(Iterator begin,int size){//древесная(пирамидальная) сортировка.
    for(int i=size/2;i;)//make heap
        _fix<Iterator,Cmp>(begin,size,--i);
    while(--size){//sort heap
        std::iter_swap(begin,begin+size);
        _fix<Iterator,Cmp>(begin,size,0);
    }
}


Что касается адаптивных сортировок, то я не вижу в них большого смысла. Ибо если мы априори знаем характер сортируемых данных то сами можем подобрать оптимальную сортировку вплоть до O(1) для уже отсортированных данных . Если же характер данных неизвестен то в среднем мы должны больше терять на выяснении этого характера.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.