вентилятор
Хорошего настроения!

Сортировка пузырьком (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





Поддержать сайт:


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

Бинарный (двоичный) поиск в массиве

Сегодня мы разберём алгоритм бинарного поиска...

Категория: Алгоритмы  Подкатегория: Разное
Дата: 06-08-2017 в 10:55:57 0


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

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

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

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

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

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

Отлично
Лучший 01-12-2018 в 17: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 в 19:08:11

Салам. Самый лучший код который я видел! Обязательно посети нашу шашлычную (Приморский просп., 93/1, Санкт-Петербург). Скажи, что ты от Алима.
Алимандум Жукчуев 19-02-2019 в 15:01:16

Спасибо) Буду в Питере - зайду)
Калужский Александр 19-02-2019 в 15:54:52

Я тоже залечу в шашлыку
Дисмас 26-02-2019 в 08:25:14

А Блок-схему к нему можно написать?..
Школьник 17-11-2020 в 11:25:32

Я тоже хочу шашлык
Иван Тишевских 08-12-2021 в 11:02:09

Здравствуйте! Почему n-1в цикле for? Запишите,пожалуйста, обучающее видео массивы на питоне и Паскале. Как задать массив, сложить элементы, поиск, обмен между перемененными
Ма 01-07-2022 в 03:15:39



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



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


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




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.