Сортировка пузырьком

    Самой простой сортировкой является сортировка пузырьком. Название метода отражает суть его алгоритма:
меньшие элементы как бы "всплывают" на поверхность, т.е в начало массива.
Итак если мы возьмём код:
  for i:=1 to n-1 do
    if a[i]>[i+1] then
    begin
       c:=a[i];
       a[i]:=a[i+1];
       a[i+1]:=c;
    end;
    В нём довольно просто разобраться, этот код является основой метода сортировки  пузырьком. Циклом for мы проходим массив от
начала и до конца сравнивая его соседние элементы и если элемент стоящий слева больше того что справа, то меняем их
местами. После того как мы пройдем весь массив самый большой элемент будет стоять на последнем месте в массиве. Но нам
требует отсортировать весь массив, для этого мы данный код должны выполнить n раз, где n - количество элементов в
массиве. В этом и есть весь метод сортировки пузырьком. Ниже приведён пример сортировки пузырьком массива по
возрастанию.

Пример реализации сортировки пузырьком на паскале:

   program sort;
   const N = 10;
   var A: array[1..N] of integer;
   i, j, c: integer;
   begin
  { здесь заполняем массив }
  { выводим исходный массив }
  for i:=1 to N-1 do
  begin
      for j:=1 to N-1 do
         if A[j] > A[j+1] then
         begin
             с := A[j];
             A[j] := A[j+1];
             A[j+1] := с;
         end;
   end;
  { выводим полученный массив }
   end.

Эффективность сортировки пузырьком

В худшем случае (когда элементы исходного массива расположены в порядке убывания) эффективность сортировки:
   C(n) =n*(n–1)/2= O(n^2),

   M(n) = n*(n–1)/2= O(n^2).