Какой на сегодняшний день наиболее оптимальный алгоритм сортировки? Массивы в памяти. Время сравнения и обмена — одного порядка. Интересует алгоритм, который ко всему прочему сортирует почти отсортированные последовательности за время меньшее чем n*log(n).
Вообщем, что у меня есть на настоящий момент: quicksort с 3-way partitioning и random pivot + insertion sort для короткий подпоследовательностей. Работает неплохо. Random pivot вроде бы даёт некоторую adaptiveness, но мне кажется, что есть более эффективные алгоритмы. Вопрос какие?
Здравствуйте, 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, но быстрым в среднем он вряд ли будет.
Здравствуйте, minorlogic, Вы писали:
M> Merge sort , который учитывает монотонность последовательности. Отсортированный и обратно отсортированный за O(n)
Merge sort медленнее quick sort'а на случайных последовательностях. Мне бы и то и другое желательно. Можно, как-либо узнать относительную отсортированность последовательности перед сортировкой, чтобы выбрать соответствующий алгоритм?
Здравствуйте, _DAle_, Вы писали:
_DA>Если волнует сложность в худшем случае, то есть introsort (тот же quicksort + insertion sort, только еще плюс переход на heapsort при достижении некоторой глубины рекурсии). Сложность в худшем случае O(nlogn).
Я такое видел в Dinkumware библиотеке. Интересно, когда (на каких последовательностях) происходит это достижение большой глубины рекурсии в quick sort'е? Вроде бы соответствующим выбором pivot можно достичь худшего случая nlogn, или я не прав? Настолько ли часто встречаются такие последовательности, что применение heapsort'а необходимо?
_DA>Насчет почти отсортированный последовательностей, есть smoothsort, но быстрым в среднем он вряд ли будет.
Здравствуйте, 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 на, например, медиану первого, последнего и среднего элементов, как изменится производительность сортировки?
Здравствуйте, alexeiz, Вы писали:
A>Здравствуйте, minorlogic, Вы писали:
M>> Merge sort , который учитывает монотонность последовательности. Отсортированный и обратно отсортированный за O(n)
A>Merge sort медленнее quick sort'а на случайных последовательностях. Мне бы и то и другое желательно. Можно, как-либо узнать относительную отсортированность последовательности перед сортировкой, чтобы выбрать соответствующий алгоритм?
Неа , не слышал , о подобной реализации , но может самому придумать ? типа пройтись по элементам и подсчитать к-во монотонных участков ?
Здравствуйте, Dmi_3, Вы писали:
D_>Здравствуйте, _DAle_, Вы писали:
_DA>>Если же генератор случайных чисел известен, то построить такую последовательность труда не представляет.
D_>ВАУ! Помоги плиз. Вот я незнаю как вырождающий пример здесь
Ну я не утверждал что мне труда не представляет , ну раз уж сказал.. Здесь файлик, в нем последовательность из всего 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;
}
построить.
_DA>Ну я не утверждал что мне труда не представляет , ну раз уж сказал.. _DA>Здесь файлик, в нем последовательность из всего 20000 интов, если скормить на вход твоей сортировке, думает относительно долго. Если раскомментарить limit, то можно заметить, что глубина достигает чего-то около 10000.
Спасибо. Правда сначала долго не мог понять почему не вырождается. У меня limit был раскомментирован. В своё оправдание замечу что такую вырождающую последовательность на практике довольно трудно получить в отличии от RSDN::sort которая вырождается уже просто на одинаковых значениях в массиве и на частично реверсированных отсортированных массивах.
_DA>Строил просто, на каждой итерации делаем так, чтобы медианный элемент был на самом деле вторым по возрастанию из всего интервала.
Я протормозил. Пытался сделать так чтобы только один элемент за итерацию отбрасывался. Сейчас доказал что это невозможно. Для тех кто захочет проверить код привожу используемую в нём tree_sort. Она тоже оперирует только сравнениями и обменами. К сожалению из-за этого ана отстаёт по производительности от std::make_heap + std::sort_heap. Но я считаю, что это разумная плата за возможность более широкого использования и гарантию отсутствия "побочных" эффектов.
Что касается адаптивных сортировок, то я не вижу в них большого смысла. Ибо если мы априори знаем характер сортируемых данных то сами можем подобрать оптимальную сортировку вплоть до O(1) для уже отсортированных данных . Если же характер данных неизвестен то в среднем мы должны больше терять на выяснении этого характера.