Сортировка методом простого обмена
Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива от начала к концу и обмене местами соседних элементов, расположенных «неправильно», то есть таких, что i<j, а А[i]>А[j].
Просмотрим весь массив. Начинаем с первой пары элементов А[1] и А[2]. Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару А[2] и А[3], и если А[2] > А[3], то меняем их местами и так далее. На первом шаге будут просмотрены все пары элементов массива А[i] и А[i+1] для i от 1 до n-1. В результате максимальный элемент массива переместиться в конец массива. Поскольку самый большой элемент находится на своём месте, рассмотрим часть массива без него, то есть с первого до (n-1)-элемента. Будем повторять предыдущие действия до тех пор, пока количество элементов в текущей части не уменьшится до 2. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.
При сортировке выполняется (n-1)-просмотр.
Пример Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 1 8 4 9.
Длина текущей части массива – n-k+1, где k – номер просмотра, i – номер проверяемой пары, номер последней пары – n-k.
 |
Первый просмотр: рассматривается весь массив.
Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.
 |
Третий просмотр: рассматриваем часть массива с первого до третьего элемента.
 |
Четвертый просмотр: рассматриваем часть массива из первого и второго элемента.
Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод также называют методом «пузырька». Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки элементы с заданным свойством всплывают на поверхность.
Пусть k – Номер просмотра (изменяется от 1 до n-1),
i – номер рассматриваемой пары,
t – промежуточная переменная для перестановки местами элементов, тогда фрагмент программы будет выглядеть так:
Begin
For k:=1 to n-1 Do {цикл по номеру просмотра}
For i:=1 to n-k Do
If A[i]>A[i+1] Then
Begin {перестановка элементов}
t:=A[i];
A[i]:=A[i+1];
A[i+1]:=t;
End;
End;
Сортировка методом простого включения
Сортировка методом простого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка этим методом производится последовательно шаг за шагом. На k-ом шаге считается, что часть массива, содержащие первые (k-1) элемент уже упорядочена, то есть A[1]≤A[2]≤A[3]≤…≤A[k-1]. Далее надо взять k-ый элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1≤ j ≤ k-1), что A[j] ≤ A[k] ≤ A[j+1]. Затем надо вставить элемент A[k] на найденное место.
С каждым шагом, отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.
Рассмотрим этот процесс на примере:
Рассматриваем часть массива из одного элемента (10). Нужно вставить в нее второй элемент массива (5), так, чтобы упорядоченность сохранилась. Так как 5<10, вставляем 5 на первое место. Отсортированная часть массива содержит два элемента.
Возьмем третий элемент массива (2) и подберем для него место в упорядоченной части массива.2<5, 2<10, следовательно его нужно поставить на нужное место.
Следующий элемент – 7. Он записывается в упорядоченную часть массива на третье место, так как 5<7, но 7<10.
Далее, действуя аналогичным образом, определяем, что 9 необходимо записать после 7 и до 10.
Определяем место для предпоследнего элемента. Место числа 4 – второе, так как 2<4, но 4<5.
Осталось подобрать подходящее место для последнего элемента. Массив отсортирован полностью.
For k:=2 To n Do {так как начинаем сортировку с поиска подходящего места для А[2]}
Begin
х:=A[k];
“вставить х на подходящее место в A[1]…A[k]”
End.