Сортировка SortBubble (SortBall)

Сортировка SortMinMax

Сортировка SortMin (SortMax)

Методы сортировки за время порядка O(n2)

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

Рассмотрим алгоритмы сортировки с квадратичной сложностью, начиная с простейших, интуитивно понятных.

Две сортировки минимумами и максимумами являются вариации алгоритма, называемого часто "простым выбором". Идея алгоритма прозрачна и состоит в том, чтобы найти минимальный (максимальный) элемент массива и поставить его на первое (последнее) место. Затем применить тот же прием к массиву без первого (последнего) элемента, повторяя эту схему, пока оставшаяся часть массива не будет состоять из одного элемента.

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

Эти две вариации одного алгоритма сортировки относят к классу "обменных сортировок". В каждом алгоритме сортировки присутствуют операции сравнения элементов и обмена элементов. Но алгоритмы могут отличаться тем, какие операции превалируют в реализации алгоритма. В сортировках прямого выбора минимумами и максимумами обмен выполняется только после того, как сделан выбор нужного элемента, требующий многократных проверок. В обменных сортировках обмен элементов является основной операцией в процессе сортировки. И те и другие методы имеют свои достоинства и, соответственно, недостатки. Операции обмена обычно более дорогие (требуют больше времени), чем операции сравнения. В этом преимущество методов прямого выбора. Но в обменных сортировках за один проход не только один элемент становится на свое место, но и другие элементы стремятся занять свои места, что позволяет ускорить сортировку.

Идея алгоритма пузырьковой сортировки SortBubble, принадлежащей классу обменных сортировок, состоит в том, чтобы, начиная с конца массива, сравнивать два соседних элемента и, если нарушается упорядоченность, производить обмен элементами - более легкий элемент меняется местами со своим соседом. Очевидно, что при первом проходе массива минимальный элемент, как самый легкий всплывет наверх, подобно пузырьку воздуха, и станет на первое место. Важно то, что при этом будут всплывать, приближаясь к своим законным местам, и другие легкие элементы. Обменные сортировки хорошо работают на почти упорядоченных массивах. Достоинство алгоритма еще и в том, что он позволяет собрать важную информацию - на каждом проходе можно подсчитывать число обменов. Если оно равно 0, то массив уже упорядочен, и сортировку можно прекращать.

Алгоритм "тяжелого шарика" SortBall является симметричной вариацией пузырьковой сортировки. Работа начинается с начала массива, и в процессе обмена вниз опускаются тяжелые элементы, так что на первом проходе максимальный элемент станет на последнее место.