Сортировка методом «пузырька»

Наиболее известным методом сортировки является сортировка массивов пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Сортировка методом пузырька основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки на примере сортировки по возрастанию более подробно.

Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Затем сравним второй с третьим, если второй больше третьего, то также поменяем их, далее сравниваем третий и четвертый, и если третий большего четвертого, меняем их местами. После трех этих сравнений самым большим элементом станет элемент с номером 4. Если продолжить сравнения соседних элементов, сравнить четвертый с пятым, пятый с шестым и т. д. до сравнения (n–1)–го и n–го элементов, то в результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, с 1-го до n-1 элемента (последний, n-й элемент, рассматривать не будем, так как он уже занял свое место). После проведения данной операции самый большой элемент оставшейся части массива станет на свое (n–1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив.

Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок–схема описанного алгоритма приведена на рис.

Рисунок: Алгоритм упорядочивания по возрастанию

методом пузырька

Для обмена двух элементов в массиве (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.

2 Сортировка выбором:

Для сортировки элементов массива по возрастанию (убыванию) можно воспользоваться алгоритмом сортировки выбора максимального (минимального) элемента.

Алгоритм выбором приведен в виде блок-схемы на рис.

Найдем в массиве самый большой элемент (блоки 2–5) и поменяем его местами с последним элементом (блок 6). После этого максимальный элемент станет на свое место. Теперь надо повторять эти действия (блоки 2–6), уменьшив количество просматриваемых элементов на единицу (блок 7), до тех пор, пока количество рассматриваемых элементов не станет равным одному (блок 8). В связи с тем что мы на каждом шаге уменьшаем количество элементов на 1, то, чтобы не потерять размер массива (N), необходимо в начале алгоритма переписать N в переменную K (блок 1) и уменьшать уже значение K.

При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме в блоке 4 достаточно знак > поменять на знак <.