Квадратичные сортировки

Сортировка - это перестановка элементов массива (списка) в заданном порядке.

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

Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
   F=0
   ЦИКЛ ДЛЯ I=1 ДО N-J-1 ШАГ 1
     ЕСЛИ A[I] > A[I+1] ТО 
       ОБМЕН A[I],A[I+1]
       F=1
   СЛЕДУЮЩЕЕ I 
   ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА   // если за проход не было обменов, 
                                // то значит все элементы 
                                // расставлены в нужном порядке
 СЛЕДУЮЩЕЕ J   
Сложность данного алгоритма: \(\displaystyle O(n^{2})\).


Дополнительная полезная информация: статья на википедии.

 

Сортировка вставками

Сортировка вставками (Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.


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

При сортировке вставками вам не обязательно иметь весь массив заранее перед сортировкой. Алгоритм может получать по одному элементу в процессе сортировки. Это очень удобно, если нам нужно добавлять больше элементов во время сортировки. Алгоритм будет вставлять новый элемент в нужное место без «повторного выполнения» сортировки всего массива.

Сортировка вставками может использоваться на практике из-за ее эффективности для небольших (~ 10 элементов) наборов данных.

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

Алгоритмическая реализация данного алгоритма
// Нулевой элемент считаем уже отсортированной последовательностью. 
// Поэтому цикл начинаем с 1
ЦИКЛ ДЛЯ I=1 ДО N-1 ШАГ 1   
   X=A[I]
   J=I
   ПОКА J>0 AND A[J-1]>X    //ищем место для вставки
     ОБМЕН A[J],A[J-1]
     J=J-1
   КОНЕЦ ПОКА 
   A[J]=X
 СЛЕДУЮЩЕЕ I   
Вычислительная сложность: \(\displaystyle O(n^{2})\).