Быстрая сортировка :-)

← →
guav © (2007-11-17 19:23) [0]

http://www.tvk-research.ru/products-research-ultrasorte/

← →
vpbar © (2007-11-17 19:27) [1]

и что где алгоритм? Вы задачу 7 из http://delphimaster.net/view/15-1195192823/ решите чтобы сложность была линейная.

← →
Anatoly Podgoretsky © (2007-11-17 19:30) [2]

> guav (17.11.2007 19:23:00) [0]

Хакерско, спаммерский сайт.

← →
guav © (2007-11-17 19:31) [3]

> [1] vpbar © (17.11.07 19:27)

это орех, а не алгоритм :)

← →
vpbar © (2007-11-17 19:31) [4]

что я решил или что по ссылке в (0)? В (0) может и орех. Хотя почему не селать сортировку быстрее...

← →
guav © (2007-11-17 19:38) [5]

> [4] vpbar © (17.11.07 19:31)

Конечно по ссылке [0]

> Хотя почему не селать сортировку быстрее...

Сортировка быстрее худшего случая QuickSort O(n^2) уже существет (сложнось до O(n*log(n))
Всегда линейной сортировки сравнением в принципе не получится.

Вот тут перечислены алгоритмы сортировки http://en.wikipedia.org/wiki/Sorting_algorithm

> [2] Anatoly Podgoretsky © (17.11.07 19:30)

Ладно, если не смешно, удалите.

← →
Anatoly Podgoretsky © (2007-11-17 19:41) [6]

> guav (17.11.2007 19:38:05) [5]

Почему наоборот смешно, но в глаза бросилась направленность сайта и помойка на нем.

← →
vpbar © (2007-11-17 19:45) [7]

А эту задачу

> 7. Дан массив A[0.. 2 * M - 1] of Integer.
> Нужно эффективно переставить элементы так, чтобы элементы
> с четными индексами находились
> в начале, с нечетными - в конце, и относительны порядок
> сохранился
> Пример: 0 1 2 3 4 5 6 7 - > 0 2 4 6 1 3 5 7

можно решить с линейной сложностью?

← →
guav © (2007-11-17 19:58) [8]

> [7] vpbar © (17.11.07 19:45)

Если использовать O(n) памяти, то это тривиально :)

А если серьёзно, то не думал над той задачей 7. Просто хотел найти какой алгоритм (quicksort или вариант introsort) используется в STL, которая идёт с MS VS 2005, случайно попал на страницу, указанную в [0], вот и решил поделится приколом. Алгоритм не мой, предъявы не ко мне :)

← →
vpbar © (2007-11-17 20:06) [9]

При использовании O(1) памяти тоже есть решение с О(N). И не очень сложное.

← →
guav © (2007-11-17 20:10) [10]

> [9] vpbar © (17.11.07 20:06)

И что ?

> . Просто хотел найти какой алгоритм (quicksort или вариант
> introsort) используется в STL,

кстати, в реализации std::sort от MS VC 2005 используется quicksort-подобый алгоритм с рекурсией только для большей половины, для меньшей используется heapsort или insertion sort. Там так и написано в коментарии "большая половина".

точнее для "меньшей половины" тоже может быть вызван quicksort но уже по условию.

А вроде есть же доказательство, что нельзя отсортировать быстрее чем за O(n log n)? Ну не считая всякие поразрядные сортировки и сортировки подсчетом, потому что они заточены под конкретный тип данных.

← →
ferr (2007-11-17 23:02) [14]

> А вроде есть же доказательство, что нельзя отсортировать
> быстрее чем за O(n log n)? Ну не считая всякие поразрядные
> сортировки и сортировки подсчетом, потому что они заточены
> под конкретный тип данных.

Если на множестве задана лишь операция сравнения, то быстрее n logn нельзя.

> ferr (17.11.07 23:02) [14]

Спасибо за уточнение :)

Быстрая сортировка :-) Найти похожие ветки