Исследование и анализ различных видов сортировок

Работа посвящена изучению и сравнительному анализу методов сортировки с учетом числа сортируемых элементов N, а также до какой степени элементы уже отсортированы.

В качестве основных критериев оценки использованы временная сложность алгоритма O(N) и объем дополнительной памяти     dS(N). В качестве дополнительных критериев — устойчивость (устойчивая сортировка не меняет взаимного расположения равных элементов) и естественность поведения (эффективность метода при обработке частично упорядоченных данных).

Все методы сортировки базируются на следующих приемах: выборка; включение; распределение; обмен; слияние. В работе рассмотрены наиболее известные алгоритмы, основанные на каждом из этих приемов:

• Сортировка методом выборки (прямая выборка; турнир с выбыванием; сортировка деревом);
• Сортировка включением (сортировка пузырьком; сортировка Шелла);
• Сортировка распределением (цифровая сортировка);
• Сортировка обменами (быстрая сортировка);
• Сортировка слиянием.

На основе исследования сделаны следующие выводы:

1.  На небольших наборах данных целесообразнее использовать сортировку включением, так как из всех методов, имеющих очень простую программную реализацию, этот на практике оказывается самым быстрым и при размерностях до нескольких тысяч дает вполне приемлемую для большинства случаев скорость работы. Еще одно преимущество этого метода заключается в том, что на частично упорядоченных данных он работает быстрее, а на практике данные, как правило, уже имеют хотя бы частичный порядок.
2.  Алгоритм пузырьковой сортировки, хотя и часто используется, но имеет плохие показатели даже среди простых методов с квадратичной сложностью.
3.  Сортировка Шелла оказывается скорее теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, и при этом не дает такой скорости, какую дают сравнимые с ним по сложности методы.
4.  При сортировке больших массивов данных лучше использовать быструю сортировку.
5.  Если же добавляется требование гарантировать приемлемое время работы метода (быстрая сортировка в худшем случае имеет сложность О(N²), хотя вероятность такого случая очень мала), то надо применять либо сортировку деревом, либо сортировку слиянием: сортировка слиянием работает быстрее, но требует дополнительную память размером порядка N.
6.  В тех же случаях, когда есть возможность использовать дополнительную память размером порядка N, имеет смысл воспользоваться сортировкой распределением.

       Научный руководитель -  к.т.н. Кирдяшов Ф.Г.