Пузырьковая сортировка

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

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

Пусть Х – одномерный массив из n элементов (чисел). Требуется отсортировать его по возрастанию значений элементов. Для реализации пузырьковой сортировки потребуется организовать два цикла: один вложенный в другой.

Во внутреннем цикле (с управляющей переменной i) будет осуществляться сравнение пар соседних элементов X(i) и X(i+1) от начала и до конца массива. Для перестановки соседних элементов потребуется дополнительная переменная А.

Во внешнем цикле будет проверяться условие окончания сортировки (по значению переменной-признака).

В качестве переменной-признака окончания сортировки можно использовать либо переменную, логического типа (со значениями True и False), либо целочисленную переменную (со значениями 0 и 1). Будем использовать переменную В целого типа. Если при проверке условия В=0, то сортировка еще не завершена. Если В=1, то сортировка закончена.

На рисунке 12 изображена блок-схема сортировки по возрастанию элементов массива Х методом пузырьковой сортировки.

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

Рис.12. Пузырьковая сортировка по возрастанию