Comments 39
Сомневаюсь, что на Хабре очень много человек всего этого не знают.
<irony>Во мне не умер наивный оптимист, да?</irony>
<irony>Во мне не умер наивный оптимист, да?</irony>
h_T=1, h_(i+1)<h_i
Ужасно смотрится. Используйте тег
<sub> </sub>для нижнего индекса.
hi+1 намного симпатичнее.
Сомневаюсь, что статья о простейших алгоритмах сортировки кому-то здесь полезна. Особенно с примерами на Паскале и неформатированным кодом.
Как минимум надо было еще написать сортировку слияниями — N*logN гарантированно, алгоритм простой. Но просит дополнительную память.
Я недавно прочитал про сортировку вычёрпыванием (bucket sort) — интересная, работает за линейное средее время, но не всегда =)
Тоже базовый алгоритм.
Кому интересны базовые алгоритмы идут читать книжку от Cormen & Co, помню тут даже ссылку давали на русский перевод.
Кому интересны базовые алгоритмы идут читать книжку от Cormen & Co, помню тут даже ссылку давали на русский перевод.
QuickSort вроде как раз базовый по самое нехочу
Я уже кажется писал, но писать то, что чуть ли не дословно, а чаще понятнее и нагляднее, можно прочитать даже в Википедии постить не следует. Вот если бы были примеры использования, плюсы минусы в различных ситуациях, интересные реализации и тд — тогда это было бы кому нибудь полезным
Я уже кажется писал, но писать то, что чуть ли не дословно, а чаще понятнее и нагляднее, можно прочитать даже в Википедии постить не следует. Вот если бы были примеры использования, плюсы минусы в различных ситуациях, интересные реализации и тд — тогда это было бы кому нибудь полезным
Где мои любимые поразрядные сортировки? :(
UFO just landed and posted this here
И на будущее, не бывает меньшей и большей половины.
Если тебе интересны алгоритмы, то тебе самая дорога в википедию или лучше в библиотеку — информации получишь больше, причем в понятной и наглядной форме.
В русской википедии некоторые алгоритмы описаны не очень подробно. К примеру сортировка пирамидой: 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
Смотри английскую версию. Если надо — подтяни англиский, все равно придется рано или поздно :)
Так я ж не для себя пишу, а для тех, кто пока не очень хорош в английском.
А я не заметил что вы автор.
Как уже сказали — это все база из любой книжки по алгоритмам. Кроме того вот такое вот текстовое представление с кодом на конкретном языке — это очень непонятно для того, кто алгоритм не знает.
Quicksort скажем проще всего пянять по картинке, а HeapSort по анимации процесса. Кроме того нужно сначала рассказть про такой тип данных как Heap, а сам алгоритм написать в псевдокоде и разбить на 3 части — Build-Max/MinHeap, Max/Min Heapify и HeapSort — все сразу будет понятнее и нагляднее.
Схемы кстати можно не рисовать, их полно в сети
Кроме самого алгоритма нужен и его анализ и возможно доказательство. Не помешает показать как его можно рандомизовать, в стандартной краткой форме представить все его основные характеристики и тд. Тогда это будет хороший топик для тех, кто не знает такого алгоритма.
Как уже сказали — это все база из любой книжки по алгоритмам. Кроме того вот такое вот текстовое представление с кодом на конкретном языке — это очень непонятно для того, кто алгоритм не знает.
Quicksort скажем проще всего пянять по картинке, а HeapSort по анимации процесса. Кроме того нужно сначала рассказть про такой тип данных как Heap, а сам алгоритм написать в псевдокоде и разбить на 3 части — Build-Max/MinHeap, Max/Min Heapify и HeapSort — все сразу будет понятнее и нагляднее.
Схемы кстати можно не рисовать, их полно в сети
Кроме самого алгоритма нужен и его анализ и возможно доказательство. Не помешает показать как его можно рандомизовать, в стандартной краткой форме представить все его основные характеристики и тд. Тогда это будет хороший топик для тех, кто не знает такого алгоритма.
UFO just landed and posted this here
Зря не описаны такие сортировки, как Поразрядная сортировка, к примеру. Сортирует за линейное время.
негодую! Хватит уже постить то, что можно прочитать в википедии, кормене, еще где-нибудь. Это же фундаментальные алгоритмы! Каждый программист это обязан знать. Такими темпами скоро и до определений массивов дойдем.
Рассказали бы лучше модификации быстрой сортировки, области применения каждой сортировки. а так это бесполезная информация.
Рассказали бы лучше модификации быстрой сортировки, области применения каждой сортировки. а так это бесполезная информация.
А вот как выглядит быстрая сортировка (или точнее — алгоритм, похожий на быструю сортировку) на функциональном языке 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]);;
Функциональное программирование определённо добро.
Этот пример стал классикой из разряда, «видите какое функциональное программирование крутое». Если набрать «сортировка Хоара f#» (или haskell), везде будет подобный пример.
Только этот алгоритм совсем не сортировка Хоара, которая использует обмены. Он кушает много памяти. Честная же реализация будет иметь много строк.
Только этот алгоритм совсем не сортировка Хоара, которая использует обмены. Он кушает много памяти. Честная же реализация будет иметь много строк.
UFO just landed and posted this here
и всё-равно абсолютно большая чать программистов будет использовать qsort() или любой другой встроенный метод сортировки и будут по-моему правы — кто-нибудь пробовал тестировать скорость работы того же qsort и собственноручно написанной быстрой сортировки? я еще не встречал людей, которым удалось бы его обогнать =)
UFO just landed and posted this here
Изобилие выражений «очевидно» и «нетрудно понять» навевает на мысль о копипасте с учебника. Либо у тебя уже такой академический стиль )
anyway, приятно видеть знакомое имя на хабре ;-)
anyway, приятно видеть знакомое имя на хабре ;-)
юзайте сортировку хоара
Sign up to leave a comment.
Ещё раз про сортировку