Сортировка массива из случайных чисел методом пузырька

ObjectOne > Pascal > Сортировка массива из случайных чисел методом пузырька

Сортировка массива из случайных чисел методом пузырька

Массив называется отсортированным по возрастанию, если для любых его элементов выполняется
условие a[i]<a[i+1]. Массив называется отсортированным по убыванию, если для любых его элементов выполняется условие a[i]>a[i+1].

Существует множество методов сортировки. Одни из них являются более эффективными, другие
проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который
также называют методом простого обмена. В чем же он заключается, и почему у него такое странное
название: «метод пузырька»?

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

При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно n-1, где n – это количество элементов массива.
Количество сравнений в каждом проходе равно n-j, где j – это номер прохода по массиву (первый, второй, третий и т.д.).
При обмене элементов массива обычно используется «буферная» (третья) переменная, куда временно помещается значение одного из элементов.

const
  n = 10; { количество элементов в массиве }
var
  a:array[1..n] of integer;
  i,j,buf:integer;
begin
{Заполняем массив случайными целыми числами от 0 до 50 и выводим массив на экран}
  for i:=1 to n do
    begin
      a[i]:=random(50);
      write(a[i]:3);
    end;
{ сортировка массива по возрастанию }
  for j:=1 to n-1 do
    for i:= 1 to n-j do {проверяем все элементы до предпоследнего неотсортированного}
      if a[i]>a[i+1] then { ищем элементы, которые стоят неправильно }
        begin { меняем элементы местами }
          buf:=a[i];
          a[i]:=a[i+1];
          a[i+1]:=buf;
        end;
  writeln;

writeln('Массив после сортировки: ');
  for i:=1 to n do write(a[i],' ');
end.

const

n = 10; { количество элементов в массиве }

var

a:array[1..n] of integer;

i,j,buf:integer;

begin

{Заполняем массив случайными целыми числами от 0 до 50 и выводим массив на экран}

for i:=1 to n do

begin

a[i]:=random(50);

write(a[i]:3);

end;

{ сортировка массива по возрастанию }

for j:=1 to n-1 do

for i:= 1 to n-j do {проверяем все элементы до предпоследнего неотсортированного}

if a[i]>a[i+1] then { ищем элементы, которые стоят неправильно }

begin { меняем элементы местами }

buf:=a[i];

a[i]:=a[i+1];

a[i+1]:=buf;

end;

writeln;

writeln('Массив после сортировки: ');

for i:=1 to n do write(a[i],' ');

end.

Количество просмотров: 11 299

| Категория: Pascal
| Тэги: сортировка

« Паскаль Сортировка по убыванию методом пузырька Случайный рандомный список из строковых значений »