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

Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.

Для проведения исследования были выбраны следующие алгоритмы сортировки:

Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).

Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).

Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).

Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n?2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n?log2n).

Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n?log2n).

Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.

Полностью неотсортированный массив:

image

Частично отсортированный массив (половина элементов упорядочена):

image

Результаты, предоставленые в графиках:

image

image

Выводы:

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

Комментарии (25)


  1. maximw
    25.12.2015 11:29
    +4

    Помимо сомнительной ценности исследования.
    1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.
    2) Где, например, сортировка Шелла?


    1. Mrrl
      25.12.2015 11:52
      +4

      Сортировка Шелла от сортировки расчёской почти не отличается.
      А вот каким образом увеличение массива до 1000 элементов приводит к увеличению памяти на 400 килобайт — действительно вопрос.
      И почему быстрая сортировка, которая проиграла всем конкурентам на всех тестах, кроме одного, объявлена победителем — совершенно неясно.
      Да и 500 миллисекунд на сортировку массива из 1000 элементов — что это? За такое время легко сортируется неупорядоченный массив длиной в 2-3 миллиона элементов. Или там делалась тысяча тестов?


    1. Imp5
      25.12.2015 22:42
      +3

      1) Диаграммы очень трудно читаются. Тут нужны столбцы, а не линии.

      Ага, график зависимости времени от алгоритма, а не от размера массива — это сильных ход.


  1. alexhemp
    25.12.2015 11:34
    +3

    Слишком мелкие выборки для такого железа и процессора.

    Возьмите миллион элементов, посмотрите что будет.
    Кроме того, quicksort без проблем реализуется без рекурсии.


    1. Mrrl
      25.12.2015 13:34
      +3

      На самом деле, вопрос интересный. Все гонятся за ускорением для большого числа элементов или за сортировочными сетями (для аппаратной реализации) — для малых, а какой алгоритм будет лучшим для 200 элементов? Число уже достаточно большое, чтобы квадратичным алгоритмам было плохо (кроме, возможно, бинарных вставок с быстрой реализацией сдвига массива). Кто победит — расчёска, быстрая сортировка, слияние?
      А чем плоха рекурсия для quicksort? Работа с аппаратным стеком может быть быстрее, чем с ручной его реализацией (а тем более, чем с библиотечной).


      1. alexhemp
        25.12.2015 17:56
        +2

        Рекурсия плоха тем что стекфрейм при CALL много больше чем индексов диапазона.

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

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

        Все еще от языка реализации зависит. Одно дело на ассемблере целые числа сортировать, а другое дело — на Scala списки :-)


        1. Mrrl
          25.12.2015 18:47
          +1

          200 элементов — не так уж мало. Если вам нужно сортировать сколько-нибудь миллиардов таких массивов, когда каждый лишний такт, затраченный на сортировку, будет влиять на производительность.
          «Первые курсовые в профильных вузах»? Ну и что. Если результат правильно получен и грамотно оформлен, то это результат. И кто-нибудь может им воспользоваться.
          Изучены вдоль и поперёк? И каким будет практический ответ на задачу, скажем, «как быстрее всего отсортировать 200 троек 64-битных чисел (при лексикографическом порядке сравнения) на 64-битном же компьютере»? Или хотя бы направление, где его искать (кроме очевидного — напишите десяток специализированных сортировок и сравните").
          Задач слишком много, чтобы считать их все решёнными. И условия, в которых они используются, постепенно меняются, так что «какие-нибудь мелочи» могут портить найденные ранее решения.


          1. alexhemp
            25.12.2015 19:32
            +1

            Это все ньюансы реализации, а не самих алгоритмов сортировки.

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

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

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

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

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


            1. Mrrl
              25.12.2015 19:55
              +1

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


              1. alexhemp
                25.12.2015 20:12
                +2

                Да причем тут все это? Вы что хотите измерить — эффективность алгоритмов сортировки? Или вашего алгоритма сравнения или обмена?

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

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

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

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

                Данная же «работа» не тянет даже на реферат студента-первокурсника. Задача не описана, результаты не соответствуют теории (которая в общем-то не вызывает сомнения, все эти алгоритмы изучены вдоль и поперек, каждый студент их реализует и не по одному разу)


                1. Mrrl
                  25.12.2015 20:35
                  +1

                  Можно написать сортировку слиянием (без дополнительной памяти), которая будет быстрее быстрой сортировки.
                  Можно после этого написать быструю сортировку, которая будет быстрее их обеих.
                  Можно оценить долю одинаковых элементов в массиве, и написать два варианта быстрой сортировки, каждый из которых (для своего случая) будет быстрее предыдущей сортировки.
                  А потом перейти на компьютер с другими параметрами кэша (или просто на другой компилятор) и обнаружить, что все времена непредсказуемым образом перемешались. Причём различия могут достигать нескольких раз.

                  Я не хочу измерить эффективность сравнения и обмена. Я хочу, чтобы пользователь ждал результата не 10, а 5 минут (на том же железе). И если ключом к эффективности окажется сортировка — придётся экспериментировать с ней. Или искать способы обойтись вообще без неё.


  1. norlin
    25.12.2015 11:59
    +3

    В этой статье явно не хватает старого видео с демонстрацией алгоритмов сортировки:

    И вот ещё одно, как раз сравнение по скорости: www.youtube.com/watch?v=ZZuD6iUe3Pc


    1. CodeRush
      25.12.2015 12:04
      +3

      И вот этого видео, конечно: www.youtube.com/watch?v=ywWBy6J5gz8


    1. zelenin
      25.12.2015 12:38
      +5

      или не хватает этого сайта sorting.at с демонстрацией семнадацати видов сортировки


  1. kosmos89
    25.12.2015 14:00
    +4

    Что-то я не понял. У сортировок с O(n^2) почему-то линейно растет время выполнения.
    Например, пузырек обработал 200 элементов за 116 мс, а 1000 — за 564, что почти в 5 раз больше. А должно было быть в 25 раз больше!
    Вы точно все правильно сделали?


    1. Singerofthefall
      25.12.2015 14:42
      +2

      Тут куча вариантов, начиная от неправильной реализации алгоритма сортировки/замеров времени выполнения, и заканчивая измерением не того, что нужно (например, вместе с сортировкой замерялась подготовка данных).

      А вообще, приводить исследование скорости работы алгоритмов и не показывать ни сами алгоритмы, ни методику измерения — это как-то не очень. Писал ли автор сортировки сам, или взял готовые решения? На каком языке, как проводились измерения времени выполнения, как подготавливались тестовые данные, ну и так далее.


  1. SKolotienko
    25.12.2015 14:09
    +6

    Сорцы в студию? Не верю я в то, что стандартный quicksort на 50-элементном массиве занимает 100мс. Вы, случаем, не в Debug ли запускали?


  1. Chaos_Optima
    25.12.2015 14:20
    +2

    Очень странные результаты, бабл сортировка быстрее и потребляет больше памяти чем qsort, очень странно. Былобы неплохо посмотреть на код. К тому же я сильно подозреваю что тестировалось всё в дебаг режиме с stl контейнерами, пол секунды на 1000 элементов это очень долго.


    1. yjurfdw
      25.12.2015 14:44
      +1

      В общем случае, время сортировки вставкой — c1*n^2, а слиянием — c2*n*log(n), где c1 < c2
      Т.е. на мелких данных быстрее отработает вставкой, чем слиянием.


      1. Mrrl
        25.12.2015 15:29
        +1

        У меня получилось, что где-то начиная с 100 элементов слияние быстрее вставки. Но алгоритмы совсем не оптимизированы.


  1. Chaos_Optima
    25.12.2015 14:35
    +5

    Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n?2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n?log2n).

    Эм… лучший случай работает медленнее среднего?.. ясно.


  1. isotoxin
    25.12.2015 14:50
    +5

    Цифры взяты с потолка.
    Какая-то отписка ради инвайта.


    1. Mrrl
      25.12.2015 15:30
      +5

      С потолка они были бы правдоподобнее.


  1. WinPooh73
    27.12.2015 14:02
    -1

    > наиболее оптимальным алгоритмом… является быстрая сортировка

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

    Да, и Comb sort — это просто другое название для сортировки Шелла, или там есть какие-то принципиальные отличия в алгоритме?


    1. Mrrl
      27.12.2015 16:42

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