Регистрация / Вход
Прислать материал

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

ФИО
Андреев Савелий Дмитриевич
Электронная почта
7c68e34f41ca123123@mail.ru
Номинация
Информационные технологии
Институт
Школа
Кафедра
Другое
ФИО научного руководителя
к.т.н. Кирдяшов Ф.Г.
Академическая группа
11 класс
Наименование тезиса
Исследование и анализ различных видов сортировок
Тезис

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

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

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

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

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

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

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