Ещё раз про сортировку

[Skiminok]

Сомневаюсь, что на Хабре очень много человек всего этого не знают.

<irony>Во мне не умер наивный оптимист, да?</irony>

[fader44]

h_T=1, h_(i+1)<h_i

Ужасно смотрится. Используйте тег

<sub> </sub>

для нижнего индекса.
h_i+1 намного симпатичнее.

[agorkov]

Спасибо, исправил.

[hardex]

Сомневаюсь, что статья о простейших алгоритмах сортировки кому-то здесь полезна. Особенно с примерами на Паскале и неформатированным кодом.

[charon]

зря сомневаетесь. Мне полезна, например.

[mihaild]

Как минимум надо было еще написать сортировку слияниями — N*logN гарантированно, алгоритм простой. Но просит дополнительную память.

[shai_xylyd]

Я недавно прочитал про сортировку вычёрпыванием (bucket sort) — интересная, работает за линейное средее время, но не всегда =)

[k_s]

Тоже базовый алгоритм.

Кому интересны базовые алгоритмы идут читать книжку от Cormen & Co, помню тут даже ссылку давали на русский перевод.

[shai_xylyd]

Там и прочитал) Раньше из линейных знал только Radix и сортировку подсчетом, они как-то больше на слуху.

[Monca]

а можно подробнее, о какой книге речь?

[hardex]

google://кормен

[FTDeBUGgeR]

www.ozon.ru/context/detail/id/2429691/
www.ozon.ru/context/detail/id/4751785/

[ekungurov]

У Кнута целый том по алгоритмам сортировки.

[ekungurov]

Хотя да, наверное этот мой комментарий слишком банален и бесполезен.

[k_s]

QuickSort вроде как раз базовый по самое нехочу

Я уже кажется писал, но писать то, что чуть ли не дословно, а чаще понятнее и нагляднее, можно прочитать даже в Википедии постить не следует. Вот если бы были примеры использования, плюсы минусы в различных ситуациях, интересные реализации и тд — тогда это было бы кому нибудь полезным

[Vas3K]

Где мои любимые поразрядные сортировки? :(

[agorkov]

И на будущее, не бывает меньшей и большей половины.

[agorkov]

Правда большая половина людей, этого не понимает. :)

[k_s]

Если тебе интересны алгоритмы, то тебе самая дорога в википедию или лучше в библиотеку — информации получишь больше, причем в понятной и наглядной форме.

[agorkov]

В русской википедии некоторые алгоритмы описаны не очень подробно. К примеру сортировка пирамидой: ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

[k_s]

Смотри английскую версию. Если надо — подтяни англиский, все равно придется рано или поздно :)

[agorkov]

Так я ж не для себя пишу, а для тех, кто пока не очень хорош в английском.

[k_s]

А я не заметил что вы автор.

Как уже сказали — это все база из любой книжки по алгоритмам. Кроме того вот такое вот текстовое представление с кодом на конкретном языке — это очень непонятно для того, кто алгоритм не знает.

Quicksort скажем проще всего пянять по картинке, а HeapSort по анимации процесса. Кроме того нужно сначала рассказть про такой тип данных как Heap, а сам алгоритм написать в псевдокоде и разбить на 3 части — Build-Max/MinHeap, Max/Min Heapify и HeapSort — все сразу будет понятнее и нагляднее.

Схемы кстати можно не рисовать, их полно в сети



Кроме самого алгоритма нужен и его анализ и возможно доказательство. Не помешает показать как его можно рандомизовать, в стандартной краткой форме представить все его основные характеристики и тд. Тогда это будет хороший топик для тех, кто не знает такого алгоритма.

[akzhan]

Зря не описаны такие сортировки, как Поразрядная сортировка, к примеру. Сортирует за линейное время.

[Rustam]

негодую! Хватит уже постить то, что можно прочитать в википедии, кормене, еще где-нибудь. Это же фундаментальные алгоритмы! Каждый программист это обязан знать. Такими темпами скоро и до определений массивов дойдем.
Рассказали бы лучше модификации быстрой сортировки, области применения каждой сортировки. а так это бесполезная информация.

[agorkov]

Быть может, каждый программист и обязан это знать, но 28 человек добавили этот топик в избранное, а значит, кому-то это всё-таки нужно, интересно, полезно.

[shwars]

А вот как выглядит быстрая сортировка (или точнее — алгоритм, похожий на быструю сортировку) на функциональном языке F#:

let rec quicksort = function
                        | [] -> []
                        | h::t -> quicksort ([ for x in t do if x<=h then yield x]) 
                                  @ [h] @ quicksort ([ for x in t do if x>h then yield x]);;

[agorkov]

Функциональное программирование определённо добро.

[megalol]

Этот пример стал классикой из разряда, «видите какое функциональное программирование крутое». Если набрать «сортировка Хоара f#» (или haskell), везде будет подобный пример.
Только этот алгоритм совсем не сортировка Хоара, которая использует обмены. Он кушает много памяти. Честная же реализация будет иметь много строк.

[VakarimaZ]

и всё-равно абсолютно большая чать программистов будет использовать qsort() или любой другой встроенный метод сортировки и будут по-моему правы — кто-нибудь пробовал тестировать скорость работы того же qsort и собственноручно написанной быстрой сортировки? я еще не встречал людей, которым удалось бы его обогнать =)

[agorkov]

Спасибо. Разумеется имеется в виду это:
h[1]:=31; h[2]:=15; h[3]:=7; h[4]:=3; h[5]:=1;

[agorkov]

А если говорить о смысле кода, то это сортировка с постоянно уменьшающимся шагом. Сначала с шагом 31, потом 15, потом 7 и т.д.

[Semy]

Изобилие выражений «очевидно» и «нетрудно понять» навевает на мысль о копипасте с учебника. Либо у тебя уже такой академический стиль )
anyway, приятно видеть знакомое имя на хабре ;-)

[stas_agarkov]

юзайте сортировку хоара