Линейные массивы

program sort2; var

a: array[0..20] of real; B: real; i, j, n: integer;

begin

WriteLn('Введите количество чисел n<=20.'); ReadLn(n);

WriteLn('Введите массив.'); for i := 1 to n do Read(a[i]);

for i := 2 to n do {начиная со второго элемента до конца массива} begin

B := a[i]; {запоминаем i-й элемент}

a[0] := B; {этот же элемент записываем в а[0] - это барьер!} j := i - 1; {индекс i запоминаем в j}

while B < a[j] do {пока очередной рассматриваемый элемент больше i-го элемента} begin

a[j + 1] := a[j]; {сдвигаем элемент} j := j - 1; {уменьшаем j на 1}

end;

a[j + 1] := B; {как только найдено место, туда записывается В} end;

WriteLn('Отсортированный массив:');

for i := 1 to n do Write(a[i]:6:2); WriteLn; end.

Метод пузырька

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

В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Алгоритм и особенности этой сортировки таковы:

1.При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.

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

3.При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

4.На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

5.В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

6.После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.

7.Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

8.При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.