Вопрос 5. Алгоритм сортировки массивов «пузырек».
Массив- это структура данных, которая представляет собой однородную, фиксированную по размеру и конфигурации совокупность элементов простой или составной структуры, упорядоченных по номерам.
Массив определяется именем (идентификатором) и количеством размерностей (координат), необходимых для указания местонахождения требуемого элемента массива.
Алгоритм:
Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход.
Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:
Program BubbleSort;
Uses Crt;
Const
N=20; {длина массива}
Type
TVector = array [1..n] of Real;
Var
Vector:TVector;
B : Real;
I, k : integer;
Begin
ClrScr;
Writeln (‘Введите элементы массива’);
For I: = 1 to n do Read (Vector[i]); Readln;
{——————————————————}
For k: =n downto 2 do
{“Всплывание”очередного максимального элемента}
{на k-ую позицию}
For I: = 1 to k-1 do
If Vector [i]>Vector [i+1] then
Begin
B: =Vector[i];
Vector[i]: =Vector [i+1];
Vector [i+1]:=B
End;
{——————————————————}
Writeln (‘Отсортированный массив’);
For i: = 1 to n do Write (Vector[i]:8:2);
Writeln;
End.
Сравнение прямых методов сортировки.
Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.
Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька»).