Наиболее известным методом сортировки является сортировка пузырьковым методом. Его популярность объясняется запоминающимся названием и простым алгоритмом.
Метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают".
Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Выполняется несколько последовательных просмотров массива от начала к концу. Если соседние элементы расположены "неправильно", то они меняются местами.
Алгоритм сортировки массива по возрастанию методом простого обмена:
Начнем просмотр с первой пары элементов ( 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; |
Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак ">" заменить на "<".