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

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

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

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

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

В табл.3.2 подробно расписан процесс упорядочивания элементов в массиве. Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n-1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок-схема описанного алгоритма приведена на рис. 3.8. Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.

Таблица 3.2. Процесс упорядочивания элементов в массиве по возрастаниюНомер элемента 1 2 3 4 5

Исходный массив 7 3 5 4 2

Первый просмотр 3 5 4 2 7

Второй просмотр 3 4 2 5 7

Третий просмотр 3 2 4 5 7

Четвертый просмотр 2 3 4 5 7

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

Рис. 3.8. Сортировка массива пузырьковым методом Рис. 3.9. Сортировка массива выбором наибольшего элемента

⇐ Предыдущая 123 Следующая ⇒