1. Гарантия nlogn
2. O(1) дополнительной памяти
3. Использует только итерации по 1 элементу (короче, чтоб на связном списке тоже работала).
Пузырёк подходит под 2 и 3, но не подходит под 1
Кусорт подходит под 2 и 3, но не подходит под 1
Сортировка кучей подходит под 1 и 2, но не подходит под 3
Сортировка слиянием подходит под 1 и 3, но не подходит под 2
Сортировка слиянием без дополнительной памяти подходит под 2 и 3, но по 1 проблемка - у неё таки n*logn*logn
Вопрос чисто академический. Потому что понятно, что для списка слияние идеально, для массивов кучей можно, а остальное вообще сортировать не надо.
Если ты умеешь quicksort за O(1) доп. памяти, есть ли проблема добавлить к нему Median of medians (en, ru(Алгоритм BFPRT) )? Получаем гарантию n*log(n).
FordPerfect
> Если ты умеешь quicksort за O(1) доп. памяти
Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут). Так что в этом смысле - умею. Просто твоя фраза звучит как подвох - будто бы в общеизвестном алгоритме не O(1) в википедийном смысле. А O(1) без рекурсии логарифмической глубины и без дополнительных структур, эмулирующих стек и тоже занимающих логарифм - не умею.
Смотрим табличку в статье: http://en.wikipedia.org/wiki/Sorting_algorithm
Из простейших алгоритмов известных мне HeapSort подходит идеально и устроен он настолько легко, что даже тарас справится с реализацией.
P.S. Если под третьим пунктом имеется в виду то, что коллекция не имеет случайного доступа, то тогда наверное никакой алгоритм не подходит. А вообще квиксорт придумывали вроде как даже для сортировки данных на магнитной ленте, где как раз случайного доступа нет.
А второй пункт наверное из разряда "я не хочу тратить лишнюю память, потому что у меня её и так всего 192 МБ на всю систему".
Zefick
/_-
правка: о, ты таки прочитал моё сообщение внимательно
квиксорт не гарантирует, нахождение медианы - мутный вопрос
FordPerfect
Почитал про нахождение медианы медиан, боюсь, что там нарушается пункт 2 или 3.
TarasB
>Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут).
Тю, так не интересно.
>Почитал про нахождение медианы медиан, боюсь, что там нарушается пункт 2 или 3.
Можешь ткнуть пальцем?
// returns the index of the median of medians. // requires a variant of select, "selectIdx" // which returns the index of the selected item rather than the value function medianOfMedians(list, left, right) numMedians = ceil((right - left) / 5) for i from 0 to numMedians // get the median of the five-element subgroup subLeft := left + i*5 subRight := subLeft + 4 if (subRight > right) subRight := right // alternatively, use a faster method that works on lists of size 5 medianIdx := selectIdx(list, subLeft, subRight, (subRight - subLeft) / 2) // move the median to a contiguous block at the beginning of the list swap list[left+i] and list[medianIdx] // select the median from the contiguous block return selectIdx(list, left, left + numMedians - 1, numMedians / 2)
Проблемы переформулировать в терминах списков не вижу.
Рекурсия - хвостовая, так что даже можно за честное O(1).
>А O(1) без рекурсии логарифмической глубины и без дополнительных структур, эмулирующих стек и тоже занимающих логарифм - не умею.
Я вроде делал:
template<typename T> void flat_qsort(T *a,int n) { T m; bool flag; int l,r,i,j,k; for( k=1;k<n;++k) if( a[k]>a[0]) std::swap( a[0],a[k]); flag=true; while( flag) { flag=false; l=0; while( l<n) { for( r=l;r<n&&a[l]>=a[r];++r); --r; if( r-l>0) { i=l;j=r; m=a[( l+r)/2]; while( i<=j) { while( i<=j&&a[i]<m) ++i; while( i<=j&&a[j]>=m) --j; if( i<j) std::swap( a[i],a[j]); } if( i>l) { flag=true; for( k=l+1;k<=j;++k) if( a[k]>a[l]) std::swap( a[l],a[k]); for( k=i+1;k<=r;++k) if( a[k]>a[i]) std::swap( a[i],a[k]); } else { std::swap( a[l],a[l+1]); for( k=l+2;k<=r;++k) if( a[k]<a[l]) std::swap( a[l],a[k]); flag|=( a[l]<a[l+1]); } } l=r+1; } } }
Корректность этого не гарантирую.
Идея - не моя.
TarasB
> Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут).
В сводной табличке всё считается и даже с учётом этого в половине алгоритмов всё равно O(1).
FordPerfect
> Можешь ткнуть пальцем?
А, если отдельно помнить left+i и left+5*i, то всё ок, согласен.
Zefick
> В сводной табличке всё считается и даже с учётом этого в половине алгоритмов
> всё равно O(1).
И каким же образом?
TarasB
Лолка, напиши особенности ключа. Может там можно будет какие частные случаи применить, и вообще сортировки за линейное время использовать.
MAMOHT-92
лолка, есть такое слово шаблон
TarasB
блжад, что ты именно сортишь? По какому-то одному полю класса? Или у тебя составной сложный ключ? Если ключ простой - это целое положительное число, вещественное от 0 до 1, строка (короче особенности) или что-то еще? Если ты ищешь серебряную пулю,, которая будет работать на чем-то гипотетическом - то фиг с тобой.
MAMOHT-92
> блжад, что ты именно сортишь?
нечто, поддерживающее сравнение и обмен местами
всё
даже копирование может не поддерживаться
TarasB
ну тогда все печально.
FordPerfect
while { while { for { while { while { while {
ясно.
Тема в архиве.