Наиболее известным методом сортировки является сортировка пузырьковым методом. Его популярность объясняется запоминающимся названием и простым алгоритмом.
Метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают".
Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Выполняется несколько последовательных просмотров массива от начала к концу. Если соседние элементы расположены "неправильно", то они меняются местами.
Алгоритм сортировки массива по возрастанию методом простого обмена:
Начнем просмотр с первой пары элементов ( a[1] и a[2] ). Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если второй больше третьего, то также меняем их, далее сравниваем третий и четвертый, и если третий больше четвертого, меняем их местами, и т.д. Последними сравниваем (n-1)ый и nый элементы. При первом обходе массива будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до (n-1). В результате максимальный элемент массива переместится в конец массива.
Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1)го элемента. Повторим предыдущие действия для этой части массива, в результате чего второй по величине элемент массива переместится на последнее место рассматриваемой части массива, то есть на ( n-1 )е место во всем массиве.
Эти действия продолжают до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.
Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент.
Ниже приведен текст процедуры сортировки массива по возрастанию методом пузырька.
|
procedure sorting2(var a:myarray); var k,i,t:integer; 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; |
Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак ">" заменить на "<”
