Здравствуйте, minorlogic, Вы писали:
M>Ну давайте не будем про технические детали ? а ? M>Я специально проговорил фразу что мы сортируем ЧИСЛА, и карточки у нас сортируются числами а не компараторами.
Ну так бы сразу и сказали, что речь пойдет о сферических конях в вакууме! А то изначальное письмо было написано в стиле "юзайте радикс-сорт — и будет вам щастье". Я собственно и хотел сказать, что щастье только у сферического коня.....
M>Вы напишете qsort O(log2 N) памяти и O(N) radix sort , замечательно. Если вас интересует как написать с меньшим расходом памяти, то вам в группу алгоритмов, если вы мне хотите доказать что я не напишу , милости прошу в группу алгоритмов, а еще лучше почитать литературу , поискать в инете и т.д.
Т.е. Вы (кст, на форумах все-таки принято общаться на "ты") хотите сказать, что радиксу надо памяти меньше чем O(N)?
M>Давайте проведем серию экспериментов с компататорами , когда у нас есть стопка конвертов , в которых лежат теже карточки но прочесть их испытуемый не может , а только отдать третьему лицу 2 карточки. M>Третье лицо (компаратор) раскрывает конверты , сравнивает и отдает обратно с результатом сравнения. Уверен что поигравшись с карточками минут 10 практически илюбой человек и квик сорот и мердж сорт придумает и т.д.
Любой нормальный человек придумает как можно обработать карточки, не сортируя их..... ИМХО опять же
Здравствуйте, xvost, Вы писали:
X>Т.е. Вы (кст, на форумах все-таки принято общаться на "ты") хотите сказать, что радиксу надо памяти меньше чем O(N)?
К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту. А для радикса и других подобных подходов нужен обязательно внешний массив O(N). Так что им можно сортировать только числа в узком диапазоне.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
Драсте-приехали. Я стэк — это что, не память?
Итак, запомни. Для быстрой сортировки требуется O(log N) памяти.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
VD>>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
На самом деле, лобовая реализация быстрой сортировки в клинических случаях требует O(N) памяти и O(N^2) времени. Не верите — проверте. Реализуем чистый, рекурсивный quick-sort без отсечки и даем ему отсортированный массив миллионов на десять. Результата не дождетесь — stack overflow гарантирован. Другое дело, что эта проблема легко решается переключением на insertion-sort на мелких кусочках. Алгоритму при этом требуется O(1) памяти, но он уже и не является быстрой сортировкой в чистом виде.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
VD>>>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
MS>На самом деле, лобовая реализация быстрой сортировки в клинических случаях требует O(N) памяти и O(N^2) времени. Не верите — проверте. Реализуем чистый, рекурсивный quick-sort без отсечки и даем ему отсортированный массив миллионов на десять. Результата не дождетесь — stack overflow гарантирован. Другое дело, что эта проблема легко решается переключением на insertion-sort на мелких кусочках. Алгоритму при этом требуется O(1) памяти, но он уже и не является быстрой сортировкой в чистом виде.
Неправда Ваша, учим мат часть. Для квик сорта нужно максимум O(log(N)) памяти. Но это, правда, при правильной реализации:
разделили стартовый интервал на два интервала
вызвали процедуру для меньшего интервала
гото в начало процедуры, но только задаем второй интервал, как стартовый, то есть как бы вызываем процедуру сортировки для второго интервала, но не делая лишнего вызова
А сортировка вставками нужна чтобы увеличить быстродействие раз в десять, так как у этой сортировки константа поменьше будет...
ЗЫ Поминаемый здесь очень часто товарищ Кнут, много написал на эту тему. В том числе привел оценку сложности модифицированного алгоритма быстрой сортировки, где в качестве параметров выступают времена выполнения той или иной операции на проце.
ЗЗЫ Где то я читал, что Кнут в последующих томах -- которые он сейчас пишит, толи уже почти написал, но еще не издал -- сделал оценки алгоритмов применительно к процу с кешем... Как нить на досуге надо будет почитать.
... << RSDN@Home 1.1.4 beta 5 rev. 411>>
"Бог не терпит голой сингулярности" -- Роджер Пенроуз
Здравствуйте, McSeem2, Вы писали:
VD>>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
MS>Драсте-приехали. Я стэк — это что, не память? MS>Итак, запомни. Для быстрой сортировки требуется O(log N) памяти.
Нда. Не ожидал такого от тебя. Через стэк передаются только границы сортируемого массива. А не сами данные. Так что для данных никакая дополнительная память не нужна. А тех граних, их мизир. Так что быстрая сотртировка позволяет сортировать массивы по месту. Об этов в любом учебнике сказано.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, McSeem2, Вы писали:
MS>На самом деле, лобовая реализация быстрой сортировки в клинических случаях требует O(N) памяти и O(N^2) времени. Не верите — проверте. Реализуем чистый, рекурсивный quick-sort без отсечки и даем ему отсортированный массив миллионов на десять. Результата не дождетесь — stack overflow гарантирован. Другое дело, что эта проблема легко решается переключением на insertion-sort на мелких кусочках. Алгоритму при этом требуется O(1) памяти, но он уже и не является быстрой сортировкой в чистом виде.
Отсортированный массив для быстрой сортировки в которой медиана берется из середины массива алгоритм не квадратичный. Более того это лучший случай. Квадратичный случай конечно есть, но в природе они практически не всречаются. Так что учить матчасть похоже нужно именно тебе. Вот хорошая ссылочка на авторитетном ресурсе
Наихудшим сценарием для «быстрой» сортировки будет тот, при котором центральный элемент все время попадает в одноэлементный подсписок, а все прочие элементы остаются во втором подсписке. Это происходит тогда, когда центральным всегда является наименьший элемент. Рассмотрим последовательность 3, 8, 1, 5, 9.
На первом проходе производится n сравнений, а больший подсписок содержит n-1 элементов. На следующем проходе этот подсписок требует n-1 сравнений и дает подсписок из n-2 элементов и т.д. Общее число сравнений равно:
n + n-1 + n-2 + ... + 2 = n(n+1)/2 — 1
Сложность худшего случая равна O(n2), т.е. не лучше, чем для сортировок вставками и выбором. Однако этот случай является патологическим и маловероятен на практике. В общем, средняя производительность «быстрой сортировки» выше, чем у всех рассмотренных нами сортировок.
Алгоритм QuickSort выбирается за основу в большинстве универсальных сортирующих утилит. Если вы не можете смириться с производительностью наихудшего случая, используйте пирамидальную сортировку – более устойчивый алгоритм, сложность которого равна O(n log2n) и зависит только от размера списка.
ЗЫ
Кстати, как показали мои эксперементы быстрая сортировка без оптимизация на сорвеменных процессорах и компиляторах обычно обгоняет "оптимизированные" версии. Так самый медленный вариант быстрой сортировки из всречавшихся мне — это qsort из MS CRT (напичканный "оптимизациями" и от того плохо читаемый).
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, xvost, Вы писали:
VD>>К сведению, для быстрой сортировки вообще дополнительная память не нужна.
X>В данном вопросе тебя постигла ошибка. Ибо
Я плякаль.
X> историю отрезков, которые надо сортировать, хранить надо. Это высота бинарного дерева, то бишь log.
Обожаю умные рассуждения при полном непонимании того о чем идет речь. На будущее... Когда говорят о дополнительной памяти имеется в виду необходимость копирования обрабатываемых данных в промежуточное хранилище. Так вот быстрая сортировка этого не требует. А вот другие логарифмические алгоритмы хотя и обеспечивают, казалось бы, сходные скоростные показатели, но при этом требуют дополнительную память. Из-за этого в 90% случаев быстрая сортировка рвет все остальные известные универсальные алгоритмы и по тому используется как основной алгоритм соритировки почти во всех современных библиотеках.
Здравствуйте, VladD2, Вы писали:
X>>В данном вопросе тебя постигла ошибка. Ибо VD>Я плякаль.
Симметрично
X>> историю отрезков, которые надо сортировать, хранить надо. Это высота бинарного дерева, то бишь log. VD>Обожаю умные рассуждения при полном непонимании того о чем идет речь. На будущее... Когда говорят о дополнительной памяти имеется в виду необходимость копирования обрабатываемых данных в промежуточное хранилище.
Когда говорят о дополнительной памяти для работы алгоритма, имеют ввиду _любую_ память, которую необходимо выделить для корректной работы алгоритма. И неважно — в куче, на стэке, etc. И для оценки кал-ва памяти используют термины "O-большое" и "O-малое". Go-go на 1й курс для изучения матчасти.
VD>Так вот быстрая сортировка этого не требует. А вот другие логарифмические алгоритмы хотя и обеспечивают, казалось бы, сходные скоростные показатели, но при этом требуют дополнительную память.
???
Приводи примеры.
Например, наиболее мною любимая сортровка Шелла требует ровно такое же кол-во памяти.
VD>Из-за этого в 90% случаев быстрая сортировка рвет все остальные известные универсальные алгоритмы и по тому используется как основной алгоритм соритировки почти во всех современных библиотеках. VD>В общем, все давно сказано до нас. Читайте Сортировка данных в массиве
Здравствуйте, VladD2, Вы писали:
VD>Так вот быстрая сортировка этого не требует. А вот другие логарифмические алгоритмы хотя и обеспечивают, казалось бы, сходные скоростные показатели, но при этом требуют дополнительную память. Из-за этого в 90% случаев быстрая сортировка рвет все остальные известные универсальные алгоритмы
Муаха-ха-ха!!!
В таком случае bubble-sort вообще должен рвать всех, ибо памяти ему нужно ровно O(1)!
С уважением, Евгений
JetBrains, Inc. "Develop with pleasure!"
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, McSeem2, Вы писали:
VD>>>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
MS>>Драсте-приехали. Я стэк — это что, не память? MS>>Итак, запомни. Для быстрой сортировки требуется O(log N) памяти.
VD>Нда. Не ожидал такого от тебя. Через стэк передаются только границы сортируемого массива.
1) Если используется рекурсивная версия.
Глубина рекурсии ~ Log(N).
Количество используемой памяти = "передаются только границы сортируемого массива" * "глубину вызовов" = O(Log(N))
2) Если использутся не рекурсивная, а итеративная версия, то индексы границ надо помнить самому на это уйдет те же O(Log(N)) памяти.
Здравствуйте, VladD2, Вы писали:
MS>>Драсте-приехали. Я стэк — это что, не память? MS>>Итак, запомни. Для быстрой сортировки требуется O(log N) памяти.
VD>Нда. Не ожидал такого от тебя. Через стэк передаются только границы сортируемого массива. А не сами данные. Так что для данных никакая дополнительная память не нужна. А тех граних, их мизир. Так что быстрая сотртировка позволяет сортировать массивы по месту. Об этов в любом учебнике сказано.
Попробую объяснить доступно.
Тебе надо начинать с теоретических основ — понятия О-нотации. О-нотация определяет лишь относительную зависимость времени/памяти от размера данных. Таким образом, O(log N) == O(0.1 * log N) == O(1000 * log N). С этой точки зрения, неважно что мы храним в стеке — данные, индексы или отдельные биты. Зависимость в любом случае остается O(log N). Не бывает такого понятия, как O(2) или O(1000). Есть только O(1). Точно так же, как не бывает O(N*1000). Есто просто O(N).
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>1) Если используется рекурсивная версия. СГ>Глубина рекурсии ~ Log(N). СГ>Количество используемой памяти = "передаются только границы сортируемого массива" * "глубину вызовов" = O(Log(N))
СГ>2) Если использутся не рекурсивная, а итеративная версия, то индексы границ надо помнить самому на это уйдет те же O(Log(N)) памяти.
Любой алгорит копирует и хранит значение переменных. Это никто в рассчет не берет. А то, что у алгоритма быстрой сортировки логарифмическое время — это и так известно.
А рекурсивный или нет для современных компиляторов без разницы. Это страшилки далекого прошлого.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, xvost, Вы писали:
X>Читайте Кнута. 3й том. Особенно оценки работы qsort'а на почти отсортированных массивах. И кого qsort пытается порвать
Спасибо за совет. Счастливо оставаться при своих заблуждениях. Если вдруг захочешь разобраться советую подумать над тем как вычислять медиану.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, qxWork, Вы писали:
W>Кстати, в реальной жизни пузырек рулит безмерно именно на почти отсортированных массивах.
Интересная у тебя жинь. Может сслочку дашь на приложение из рельной жизни занимающееся такой фигней?
С понятием "почти" в компьютерах очень фигово. Оно обычно встречается у теоретиков. А вот в реальной жизни или просто вставляют элемент в нужную позицию, если вставок мало. Или применяют ту же быструю сортировку.
Во преки бытующему тут заблуждению быстрая сортировка на отсортированном массиве не худший, а лучший случай для этого алгоритма.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, McSeem2, Вы писали:
VD>>>К сведению, для быстрой сортировки вообще дополнительная память не нужна. Ну, кроме разве что переменной для обмена значений. Быстрая сортировка сортирует по месту.
MS>На самом деле, лобовая реализация быстрой сортировки в клинических случаях требует O(N) памяти и O(N^2) времени. Не верите — проверте. Реализуем чистый, рекурсивный quick-sort без отсечки и даем ему отсортированный массив миллионов на десять. Результата не дождетесь — stack overflow гарантирован. Другое дело, что эта проблема легко решается переключением на insertion-sort на мелких кусочках. Алгоритму при этом требуется O(1) памяти, но он уже и не является быстрой сортировкой в чистом виде.
Чистый quick-sort можно реализовать так, что концевая рекурсия будет иметь дело с более длинным поддиапазоном. После чего концевую рекурсию превратим в итерацию, и получим, что максимальная глубина (в "худшем" случае) равна log2(N).
Для 4Г элементов (т.е. если мы захотим отсортировать все байты в памяти), это всего лишь 32. Нам хватит даже микроконтроллера
Здравствуйте, VladD2, Вы писали:
VD>Любой алгорит копирует и хранит значение переменных. Это никто в рассчет не берет. А то, что у алгоритма быстрой сортировки логарифмическое время — это и так известно.
Так скажем, пока глубина рекурсии (и расходы на стек) логарифмические (желательно, чтобы основание логарифма было >= 2) — этого действительно никто в расчёт брать не будет.
Но если вдруг кто-то зарядит рекурсию глубиной хотя бы в n^0.5 — будет очень печально...
А вот цитата от туда по поводу худшего случая:
Перекуём баги на фичи!
