Алгоритм сортировки пузырьком

1. Задать массив из n чисел.

2. Для номера_просмотра (k) от 1 до n -1 выполнить

2.1. Для номера_элемента (i) от 1 до n - k выполнить

Если элементы i -тый и (i +1)-вый стоят неправильно, то

Поменять их местами;

3. Вывести отсортированный массив.

4. Закончить.

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

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

Алгоритм ускоренной сортировки пузырьком

 

1. Задать массив из n чисел.

2.1 Номер_просмотра (k) = 1.

2.2. Повторять

2.2.1. Перестановка = ложь.

2.2.2. Для i от 1 до n-k выполнить

Если элементы i -тый и (i +1)-вый стоят неправильно, то

a) Поменять местами i -тый и (i +1)-вый элементы;

b) Перестановка = истина.

2.2.3. k = k +1

Пока Перестановка.

3. Вывести отсортированный массив.

4. Закончить.

Алгоритм 2.Сортировка вставками

 

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

Словесное описание алгоритма можно представить так.

Алгоритм сортировки вставками

 

1. Задать исходный массив А из n элементов, например, с помощью генератора случайных чисел.

2. Для i от 0 до n

2.1. Индекс элемента в конце массива j = i

2.2. Пока (j > 0) И (А_{j- 1} > A_i)

2.2.1. Сдвиг большего элемента, чтобы было место для вставки

А_j = А_{j- 1}

2.2.2. j = j - 1

2.3. Вставка j - го элемента на его место

А_j = A_i

3. Вывести массив А.

Время сортировки можно сократить, если учесть, что начальная часть массива (до индекса j) упорядочена. При этом точку вставки можно найти методом деления пополам диапазона индексов этой части (от 0 до j).

Алгоритм сортировки двоичными вставками

 

1. Задать исходный массив А из n элементов.

2. Для i от 0 до n

2.1. Вставляемый элемент х = A_i

2.2. Левая граница диапазона L = 0.

2.3. Правая граница диапазона R =i.

2.4. Пока (L<R)

2.4.1.Искомый индекс m = (L + R)/2

2.4.2.Если A_m ≤ x

L = m + 1

Иначе

R = m.

2.5. Перепись элементов на одну позицию в конец массива (освобождение места для вставки)

2.5.1.Для j от i до R + 1 с шагом -1

А_j = А_{j- 1}

2.6. Вставка последнего элемента

А_R= x

3. Вывести массив А.

Число сравнений и пересылок рассмотренным методом в худшем случае пропорционально n*log(n), т.е. сложность алгоритма равна О(n*log(n)).

 

Алгоритм 3. Сортировка выбором

 

Этот метод – один из наиболее простых. Он требует выполнения n -1 просмотра массива. Во время k -го просмотра выявляется наименьший элемент, который затем меняется местами с k -м.

Алгоритм сортировки выбором

1. Задать массив А из n чисел.

2. Для k от0 до n -1

2.1. j = k

2.2. Для i от k + 1 до n-1

2.2.1. Если A_i < A_j,

j = i.

2.3. Если k ≠ j, то

Поменять местами A_k и A_j.

3. Вывести массив A.

4. Закончить.

 

Алгоритм 4. Сортировка Шейкером

 

Если данные сортируются не в оперативной памяти, а на жестком диске, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений. За один проход из всех элементов выбираются минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный - в конец. Таким образом, за каждый проход два элемента оказываются на своих местах, поэтому понадобится n /2 проходов, где n — количество элементов.

На каждом проходе массив просматривается слева направо до середины, а потом – наоборот (справа налево). В результате, как при сортировке «пузырьком», при просмотре слева направо максимальный элемент попадает на свое место, а при обратном – минимальный.