Быстрая сортировка слиянием
На пальцах:
Идея :сортировать массив из двух элементов очень просто и быстро.
1. Разбиваем массив на пары и сортируем в них
2. Соединяем пары в четверки. (Алгоритм построения из двух упорядоченных массивов третьего тривиален. Просто сравниваем элементы и нужные добавляем)
3. Соединяем четверки в восьмерки и тд
Памяти: еще один массив такой же длины (на каждом шаге либо из первого во второй записывать либо из второго в первый)
Память нужна обязательно, тк иначе алгоритм слияния двух отсортированных массивов не построить.
Идея :сортировать массив из двух элементов очень просто и быстро.
1. Разбиваем массив на пары и сортируем в них
2. Соединяем пары в четверки. (Алгоритм построения из двух упорядоченных массивов третьего тривиален. Просто сравниваем элементы и нужные добавляем)
3. Соединяем четверки в восьмерки и тд
Памяти: еще один массив такой же длины (на каждом шаге либо из первого во второй записывать либо из второго в первый)
Память нужна обязательно, тк иначе алгоритм слияния двух отсортированных массивов не построить.
Прости за тормозню, что-то не очень очевидно, как строить упорядоченный массив из двух упорядоченных. Это ведь надо делать за n операций...
насколько помню. есть три указателя (номера элементов как бы первых) по массивам. Два на исходные. Один на результирующий.
Сравниваем элементы соответствующие двум указателям и больший (меньший) записываем на место
куда указывает третий указатель. сдвигаем что надо и дальше. Когда один из массивов закончиться второй
просто дописывам
ЗЫ: насколько помню там только операции сравнения считаются. Их как раз сумма длин исходных будет
Сравниваем элементы соответствующие двум указателям и больший (меньший) записываем на место
куда указывает третий указатель. сдвигаем что надо и дальше. Когда один из массивов закончиться второй
просто дописывам
ЗЫ: насколько помню там только операции сравнения считаются. Их как раз сумма длин исходных будет
Напрмер, если есть два массива 1,3,5,7,9 и 2,4,6,8,10, то слияние займет 5 операций. Это худьший случай для массивов длины 5, да?
Да
Санькс.
Напрмер, если есть два массива 1,3,5,7,9 и 2,4,6,8,10, то слияние займет 5 операций.не 5, а 10
сумма длин...
Сорри, ступил.
Однако в среднем квиксорт делает сортировку слиянием за счёт значительно меньшей константы.
А какой алгоритм хорош для "досортировки", когда обычно в целом элементы упорядочены, но локально есть небольшие отклонения, т.е. число элементов не на своих местах много меньше общего числа элементов.
Также интересует случай, когда число элементов не очень большое, например, меньше 100. Для какого существует наиболее эффективная реализация с точки зрения операций с памятью, но т.е. реально на практике.
Также интересует случай, когда число элементов не очень большое, например, меньше 100. Для какого существует наиболее эффективная реализация с точки зрения операций с памятью, но т.е. реально на практике.
Пузырёк! Если в массиве мало инверсий, скажем m, а всего элементов n, то трудоемкость будет порядка m n.
Кстати стандартный С-шный qsort использует пузырёк для коротких массивов (порядка 8 элементов).
Вообще есть мега-метод: если не уверен, что qsort не начнёт вдруг тормозить на твоих данных, можно за линейно время их рандомно перемешать и потом сортировать =)
Вообще есть мега-метод: если не уверен, что qsort не начнёт вдруг тормозить на твоих данных, можно за линейно время их рандомно перемешать и потом сортировать =)
хммм. когда я читал про слияние и qsort, то там сложности были nlogn и Cnlogn, где C скажем так в среднем где-то порядка 6. Что явно хреновее, чем слияние.
In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case.
если достаточно памяти, помнится, можно использовать сортировку вставкой (ни разу не писал у нее линейная трудоемкость
напомню, что сложность сортировки определяется не только кол-вом сравнений, но и:
1. кол-вом присваиваний
2. кол-вом дополнительной памяти
например, у слияния - очень высокое кол-во присваиваний (n^2) и доп. память порядка n элементов
1. кол-вом присваиваний
2. кол-вом дополнительной памяти
например, у слияния - очень высокое кол-во присваиваний (n^2) и доп. память порядка n элементов
насчёт присваиваний, может и соглашусь. А вот память --- это, простите, другой показатель. Не трудоёмкость уже.
> Не трудоёмкость уже
да хоть горшком назови...
т.е. можно поспорить, как это назвать и куда отнести...
но главное, что факт остается фактом - что разные алгоритмы требуют разный объем доп. памяти, соответственно при сортировке больших массивов требования к наличию доп. памяти - могут быть довольно накладными.
да хоть горшком назови...
т.е. можно поспорить, как это назвать и куда отнести...
но главное, что факт остается фактом - что разные алгоритмы требуют разный объем доп. памяти, соответственно при сортировке больших массивов требования к наличию доп. памяти - могут быть довольно накладными.
если достаточно памяти, помнится, можно использовать сортировку вставкой (ни разу не писал у нее линейная трудоемкостьСортировки быстрее чем за nlogn (в худшем случае, с произвольными данными и стандартной операцией сравнения) не бывает, что несложно доказать, только я не помню, как именно =(
через количество перестановок это доказывается
если достаточно памяти, помнится, можно использовать сортировку вставкой (ни разу не писал у нее линейная трудоемкостьу сортировки вставкой трудоемкость квадратичная. Вы еще забыли сортировку подсчетом
O(n+m) n - чилос элементов массиова, m - число различных значений, которые может принимать элемент массиова. Памяти ей надо O(m).
> у слияния - очень высокое кол-во присваиваний (n^2)
бред
> и доп. память порядка n элементов
не обязательно
бред
> и доп. память порядка n элементов
не обязательно
> Сортировки быстрее чем за nlogn (...) не бывает
Наглая ложь.
---
...Я работаю антинаучным аферистом...
Наглая ложь.
---
...Я работаю антинаучным аферистом...
Наглая ложь.Да, если заменить "(в худшем случае, с произвольными данными и стандартной операцией сравнения)" на "(...)", то получится наглая ложь. Именно поэтому в моём комментарии написано "(в худшем случае, с произвольными данными и стандартной операцией сравнения)", а не "(...)".
Да, возможно ты и прав. Я только помню, что при некоторых ограничениях на массив возможна сортировка за O(n). Только не помню, какие это были ограничения. Кажется, все элементы массива должеы принадлежать множеству значений с известным (небольшим) числом элементов.
Вообще, надо кафедральные мехматовские методички по этому поводу посмотреть. Валединский и компания.
Вообще, надо кафедральные мехматовские методички по этому поводу посмотреть. Валединский и компания.
Количество памяти -- это другой из двух важнейших параметров алгоритма наряду с трудоёмкостью. Обычно количество памяти и трудоемкость обратно пропорциональны (грубо говоря). поэтому в зависимости от ситуации берут тот или другой алгоритм.
Ну да, можно просто сосчитать вхождения каждого значения. Только тогда нужно еще задуматься, а нужен ли такой отсортированный массив, мб лучше как-то по другому хранить, например, как упорядоченную последовательность значение + число элементов <= этому значению.
Кажется, все элементы массива должеы принадлежать множеству значений с известным (небольшим) числом элементов.Именно так. Тогда можно за O(n) отсортировать
За линейное время можно сортировать и большие текстовые таблицы.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
> бред
согласен, тормознул
присваиваний - n * log n
>> и доп. память порядка n элементов
> не обязательно
приведи пример реализации
согласен, тормознул
присваиваний - n * log n
>> и доп. память порядка n элементов
> не обязательно
приведи пример реализации
типа если мы сортируем не настоящие массивы, а списки, то можно обойтись константной памятью: элементы просто будут кочевать из списка в список
в общем, зависит от языка и от машины (м.б. виртуальной)
при использовании языка с GC вроде как преимуществ у qsort я не вижу
в общем, зависит от языка и от машины (м.б. виртуальной)
при использовании языка с GC вроде как преимуществ у qsort я не вижу
> типа если мы сортируем не настоящие массивы, а списки, то можно обойтись константной памятью: элементы просто будут кочевать из списка в список
как бы да, только список по сравнению с массивом - как раз и использует память порядка n.
> при использовании языка с GC вроде как преимуществ у qsort я не вижу
GC как раз не любит списки, поэтому в системах с GC "массивные" структуры данных и соотственно алгоритмы, которые используют эти "массивные" структуры предпочтительнее, чем списочные структуры данных
как бы да, только список по сравнению с массивом - как раз и использует память порядка n.
> при использовании языка с GC вроде как преимуществ у qsort я не вижу
GC как раз не любит списки, поэтому в системах с GC "массивные" структуры данных и соотственно алгоритмы, которые используют эти "массивные" структуры предпочтительнее, чем списочные структуры данных
> как бы да, только список по сравнению с массивом - как раз и использует память порядка n
виртуальные машины тоже добавляют оверхед такой - на боксы всякие и теги
а также MMU в процессоре
> GC как раз не любит списки
смотря какой и в каких задачах
например, если у нас много таких массивов разной длины, то искать для них непрерывные куски памяти может быть напряжно, в то время как выделять память под маленькие элементы любой нормальный аллокатор умеет очень эффективно
виртуальные машины тоже добавляют оверхед такой - на боксы всякие и теги
а также MMU в процессоре
> GC как раз не любит списки
смотря какой и в каких задачах
например, если у нас много таких массивов разной длины, то искать для них непрерывные куски памяти может быть напряжно, в то время как выделять память под маленькие элементы любой нормальный аллокатор умеет очень эффективно
> виртуальные машины тоже добавляют оверхед такой - на боксы всякие и теги
наверное, да, а может и нет.
я только не понял - как из этого следует, что слияние на списках не требует на O(n) памяти больше, чем qsort на массиве.
> например, если у нас много таких массивов разной длины, то искать для них непрерывные куски памяти может быть напряжно
так именно поэтому часто используют структуры данных в виде - ArrayList-ов (список массивов)
наверное, да, а может и нет.
я только не понял - как из этого следует, что слияние на списках не требует на O(n) памяти больше, чем qsort на массиве.
> например, если у нас много таких массивов разной длины, то искать для них непрерывные куски памяти может быть напряжно
так именно поэтому часто используют структуры данных в виде - ArrayList-ов (список массивов)
> я только не понял - как из этого следует, что слияние на списках не требует
> на O(n) памяти больше, чем qsort на массиве
а нельзя это сравнивать, если разные машины
типа если писать на С в условиях фиксированной памяти, то qsort лучше
если на Lisp списки сортировать, то merge наверняка будет эффективнее, так как там VM заточена под выделение и освобождение cons
> на O(n) памяти больше, чем qsort на массиве
а нельзя это сравнивать, если разные машины
типа если писать на С в условиях фиксированной памяти, то qsort лучше
если на Lisp списки сортировать, то merge наверняка будет эффективнее, так как там VM заточена под выделение и освобождение cons
Плюс еще нужно помнить, что в варианте со списком +12 байт (а то и все +16 байт) на элемент по сравнению с массивом. Придется извращаться со списком в массиве.
Такой вопрос. У меня на практике часто возникает необходимость сортировать массивы. Но длина в них ограничена, т.е. можно завести дополнительный массив для использования при сортировке слиянием, и при необходимости, если сортируемый массив больше дополнительного массива, его увеличивать. Будет ли такой вариант лучше qsort? А если у меня к тому же операция сравнения сложная?
Однако в среднем квиксорт делает сортировку слиянием за счёт значительно меньшей константы.AFAIK в среднем quicksort имеет ту же асимптотику n*ln(n но в худшем случае квадратичен
а вот merge_sort, heap_sort (который в отличие от merge_sort не требует дополнительной памяти) в худшем случае имеют асимптотику n*ln(n но в среднем хуже коэффициент чем у quicksort
Оставить комментарий
Missi4ka
Якобы сабж позволяет всегда обеспечивать сложность n log n в отличии от обычной quicksort делением, где трудоемкость в "плохих" случаях порядка n^2.Поясните на пальцах алгоритм, плиз, или подскажите инфу по сабжу.