How to become an author
Search
Write a publication
Pull to refresh

Comments 25

Сортировка Шелла от сортировки расчёской почти не отличается.
А вот каким образом увеличение массива до 1000 элементов приводит к увеличению памяти на 400 килобайт — действительно вопрос.
И почему быстрая сортировка, которая проиграла всем конкурентам на всех тестах, кроме одного, объявлена победителем — совершенно неясно.
Да и 500 миллисекунд на сортировку массива из 1000 элементов — что это? За такое время легко сортируется неупорядоченный массив длиной в 2-3 миллиона элементов. Или там делалась тысяча тестов?
Total votes 6: ↑5 and ↓1+4
1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.

Ага, график зависимости времени от алгоритма, а не от размера массива — это сильных ход.
Total votes 3: ↑3 and ↓0+3
Слишком мелкие выборки для такого железа и процессора.

Возьмите миллион элементов, посмотрите что будет.
Кроме того, quicksort без проблем реализуется без рекурсии.
Total votes 3: ↑3 and ↓0+3
На самом деле, вопрос интересный. Все гонятся за ускорением для большого числа элементов или за сортировочными сетями (для аппаратной реализации) — для малых, а какой алгоритм будет лучшим для 200 элементов? Число уже достаточно большое, чтобы квадратичным алгоритмам было плохо (кроме, возможно, бинарных вставок с быстрой реализацией сдвига массива). Кто победит — расчёска, быстрая сортировка, слияние?
А чем плоха рекурсия для quicksort? Работа с аппаратным стеком может быть быстрее, чем с ручной его реализацией (а тем более, чем с библиотечной).
Total votes 3: ↑3 and ↓0+3
Рекурсия плоха тем что стекфрейм при CALL много больше чем индексов диапазона.

Кроме того — 200 элементов это настолько мало при сегодняшних кэшах процессоров, что и говорить нечего. Все упирается в итоге в какие-нить мелочи, вроде эффективности swap операции.

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

Все еще от языка реализации зависит. Одно дело на ассемблере целые числа сортировать, а другое дело — на Scala списки :-)
Total votes 2: ↑2 and ↓0+2
200 элементов — не так уж мало. Если вам нужно сортировать сколько-нибудь миллиардов таких массивов, когда каждый лишний такт, затраченный на сортировку, будет влиять на производительность.
«Первые курсовые в профильных вузах»? Ну и что. Если результат правильно получен и грамотно оформлен, то это результат. И кто-нибудь может им воспользоваться.
Изучены вдоль и поперёк? И каким будет практический ответ на задачу, скажем, «как быстрее всего отсортировать 200 троек 64-битных чисел (при лексикографическом порядке сравнения) на 64-битном же компьютере»? Или хотя бы направление, где его искать (кроме очевидного — напишите десяток специализированных сортировок и сравните").
Задач слишком много, чтобы считать их все решёнными. И условия, в которых они используются, постепенно меняются, так что «какие-нибудь мелочи» могут портить найденные ранее решения.
Total votes 1: ↑1 and ↓0+1
Это все ньюансы реализации, а не самих алгоритмов сортировки.

Когда вы сортируете несколько миллиардов объектов, то причем тут внутренняя сложность этих объектов? Массивы они там или нет — это не важно.

А если есть вопрос сортировки массивов малой длины — то вопрос нужно ставить именно так — и изучать практическую реализацию в реальных условиях. И поверьте — сортировка, реализованная на C++ или на Java или на каком-нить Rust даст вам дико разные результаты — как раз потому что ваши массивы — они не сферические в вакууме а имеют тоже внутреннюю организацию.

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

Но очевидно, что если у него нет большой разницы на размерах порядка 10^2-10^3 то причина не в алгоритмах, а в реализации и среде исполнения.

А сами алгоритмы изучены вдоль и поперек, откройте Кнута, том третий :-)

Total votes 1: ↑1 and ↓0+1
Внутренняя сложность при том, что у объектов может быть разное время, требующееся на сравнение (относительно времени на пересылку), разные сценарии обращения к памяти при сравнении, разная нагрузка на регистры процессора в ситуации, когда объект помещается в локальную переменную… Иногда выгоднее сортировать сам массив объектов, иногда — массив индексов, ссылающихся на элементы первого массива. Иногда можно разложить операцию сравнения на части (например, сначала отсортировать строки по первому элементу — здравствуй, радикс-сортировка), иногда нельзя.
Я говорил не про сортировку массива из миллиардов объектов, а именно про сортировку большого числа коротких массивов. Например, при построении каких-нибудь дескрипторов точек изображения. И там как раз могли возникать пограничные случаи. Конечно, в первых версиях я воспользуюсь стандартной сортировкой, но если анализ покажет, что она является узким местом — то здесь бы и пригодилась курсовая работа с анализом разных ситуаций и языков…
А то, что автор вполне мог измерять время печати на консоль или вообще запуска программы — бывает и такое. У меня компилятор иногда переставлял обращение к часам с вызовом функции сортировки — получалось нулевое время при любом размере массива. Было весело :)
Total votes 1: ↑1 and ↓0+1
Да причем тут все это? Вы что хотите измерить — эффективность алгоритмов сортировки? Или вашего алгоритма сравнения или обмена?

Ну да, общее время выполнения зависит от операции сравнения и от операции обмена. Но это и есть «операция» в вычислительной сложности алгоритма, именно в этих «операциях» над элементарными объектам она и измеряется. И она не меняется, какими бы они не были.

Ответ в общем виде очевиден — для общей памяти — quicksort, для внешней памяти (когда данные в память одной машины не влезает) — сортировка слиянием (их тоже не один вид кстати).
Есть разные тонкие случаи вроде сортировки целых чисел подсчетом, но это уже хаки.

Каждый кто открывал хотя-бы Вирта ответ этот знает, т.к. алгоритмы сортировки и поиска — одни из простейших.

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

Данная же «работа» не тянет даже на реферат студента-первокурсника. Задача не описана, результаты не соответствуют теории (которая в общем-то не вызывает сомнения, все эти алгоритмы изучены вдоль и поперек, каждый студент их реализует и не по одному разу)
Total votes 2: ↑2 and ↓0+2
Можно написать сортировку слиянием (без дополнительной памяти), которая будет быстрее быстрой сортировки.
Можно после этого написать быструю сортировку, которая будет быстрее их обеих.
Можно оценить долю одинаковых элементов в массиве, и написать два варианта быстрой сортировки, каждый из которых (для своего случая) будет быстрее предыдущей сортировки.
А потом перейти на компьютер с другими параметрами кэша (или просто на другой компилятор) и обнаружить, что все времена непредсказуемым образом перемешались. Причём различия могут достигать нескольких раз.

Я не хочу измерить эффективность сравнения и обмена. Я хочу, чтобы пользователь ждал результата не 10, а 5 минут (на том же железе). И если ключом к эффективности окажется сортировка — придётся экспериментировать с ней. Или искать способы обойтись вообще без неё.
Total votes 1: ↑1 and ↓0+1
или не хватает этого сайта sorting.at с демонстрацией семнадацати видов сортировки
Total votes 5: ↑5 and ↓0+5
Что-то я не понял. У сортировок с O(n^2) почему-то линейно растет время выполнения.
Например, пузырек обработал 200 элементов за 116 мс, а 1000 — за 564, что почти в 5 раз больше. А должно было быть в 25 раз больше!
Вы точно все правильно сделали?
Total votes 4: ↑4 and ↓0+4
Тут куча вариантов, начиная от неправильной реализации алгоритма сортировки/замеров времени выполнения, и заканчивая измерением не того, что нужно (например, вместе с сортировкой замерялась подготовка данных).

А вообще, приводить исследование скорости работы алгоритмов и не показывать ни сами алгоритмы, ни методику измерения — это как-то не очень. Писал ли автор сортировки сам, или взял готовые решения? На каком языке, как проводились измерения времени выполнения, как подготавливались тестовые данные, ну и так далее.
Total votes 2: ↑2 and ↓0+2
Сорцы в студию? Не верю я в то, что стандартный quicksort на 50-элементном массиве занимает 100мс. Вы, случаем, не в Debug ли запускали?
Total votes 6: ↑6 and ↓0+6
Очень странные результаты, бабл сортировка быстрее и потребляет больше памяти чем qsort, очень странно. Былобы неплохо посмотреть на код. К тому же я сильно подозреваю что тестировалось всё в дебаг режиме с stl контейнерами, пол секунды на 1000 элементов это очень долго.
Total votes 2: ↑2 and ↓0+2
В общем случае, время сортировки вставкой — c1*n^2, а слиянием — c2*n*log(n), где c1 < c2
Т.е. на мелких данных быстрее отработает вставкой, чем слиянием.
Total votes 1: ↑1 and ↓0+1
У меня получилось, что где-то начиная с 100 элементов слияние быстрее вставки. Но алгоритмы совсем не оптимизированы.
Total votes 1: ↑1 and ↓0+1
Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).

Эм… лучший случай работает медленнее среднего?.. ясно.
Total votes 5: ↑5 and ↓0+5
Цифры взяты с потолка.
Какая-то отписка ради инвайта.
Total votes 5: ↑5 and ↓0+5
С потолка они были бы правдоподобнее.
Total votes 5: ↑5 and ↓0+5
> наиболее оптимальным алгоритмом… является быстрая сортировка

А чем «наиболее оптимальный» отличается от просто «оптимального»?

Да, и Comb sort — это просто другое название для сортировки Шелла, или там есть какие-то принципиальные отличия в алгоритме?
Total votes 1: ↑0 and ↓1-1
Отличия, на первый взгляд, минимальные — вместо того, чтобы для каждого шага гнать пузырёк до конца, там для всех шагов, кроме последнего, выполняется только по одному обмену для каждой пары с нужной разностью индексов. Но это почему-то приводит к заметному выигрышу в эффективности.
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr