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

Всем привет!

Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.

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

Плюсы:

• Простота реализации алгоритма
• Красивое название

Минусы:

• Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n²)
• Почти не применяется в реальной жизни (используется в основном в учебных целях)

Пусть есть у нас некий массив: 3 1 4 2

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

Вернемся к нашему массиву :3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два - значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился - он всё равно, после прохождения циклом всего массива, будет последним. Аналогия - как пузырёк воздуха всплывает в воде - так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.

Сравниваем "1" и "3" - ничего не меняем.
Сравниваем "3" и "2" - Три больше двух, значит меняем местами. Получается :1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла - значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй - видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.



Теперь осталось запрограммировать данный алгоритм на языке Pascal.

const n = 4; {Заводим константу, это будет длина массива}
var i, j, k :integer; {Две переменные для вложенного цикла, одна для того чтобы элементы менять местами } 
m:array[1..n] of integer; {Заводим массив}
begin

{Будем запрашивать массив с клавиатуры:}
Writeln('Введите массив:');
for i:=1 to n do begin
  Writeln(i, ' элемент:'); 
  Readln(m[i]);
end;

{Внешний цикл отвечает за то, что мы должны повторить
 внутренний цикл столько раз, сколько у нас элементов
 массива минус 1.}
for i:=1 to n-1 do begin
  {Внутренний цикл уже перебирает элементы и сравнивает между собой.}
  for j:=1 to n-i do begin
    {Если элемент, больше следующего, то меняем местами.}
    if m[j]>m[j+1] then begin
      k:=m[j];
      m[j]:=m[j+1];
      m[j+1]:=k;
    end;
  end;
end;

{Выводи результат:}
for i:=1 to n do
Write(m[i], ' ');


end.

Вот результат:

А вот видеоурок