Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


Всем привет!

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

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


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

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

Пусть есть у нас некий массив: 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.

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


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



05-06-2016 в 15:04:48





Похожая статья:

Задача по информатике. Гуси и кролики.

Всем привет! Сегодня решим задачу по информатике "Гуси и кролики"...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0


Комментарии:

АААА
Саша 16-09-2017 в 10:49:43

я задачку решил)))
ываапсм 02-04-2018 в 18:36:11

И я решил задачку))) Классное и понятное объяснение метода!
Андрей 26-06-2018 в 16:39:48

Большое спасибо !
Юрий 19-10-2018 в 08:55:24

Спасибо. Всё понял
Денис 27-11-2018 в 21:16:26

Отлично
Лучший 01-12-2018 в 20:58:22

Чёт не получилось: program U; const N=4; var a: array [1..N] of integer; j, i, c, k: integer; begin cls; for j:=1 to N do read(a[i]); for j:=1 to N do write(a[i],' '); writeln; for i:=1 to n-1 do begin for j:=1 to n-i do begin if a[j]>a[j+1] then begin k:=a[j]; a[j]:=a[j+1]; a[j+1]:=k; end; end; end; for i:=1 to n do Write(a[i], ' '); end.
Я ваша тётя 09-12-2018 в 22:08:11



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике. Задание 1
Присылайте ваши задачи


Подготовка к
ОГЭ


Подготовка к ОГЭ по информатике


Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy