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

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

Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке — это сортировка методом пузырька, которую также называют сортировкой простого обмена.

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

Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх.

Теперь подробнее о самом алгоритме. Все достаточно просто:

  1. Для сортировки используется 2 цикла, один вложен в другой. Один используется на шаги, другой на под-шаги.
  2. Суть алгоритма — это сравнение двух элементов. Именно двух. Поясняю, например имеем массив с 10-ю элементами. Элементы будут сравниваться парами: 1 и 2, 2 и 3, 3 и 4, 4 и 5, 6 и 7 и т.д. При сравнении пар, если предыдущий элемент оказался больше чем последующий — то их меняют местами. Например если второй элемент равен 5, а третий 2, то они их поменяют местами.
  3. Сортировка методом пузырька делится на шаги. В каждом шаге выполняется попарное сравнение. В результате каждого шага наибольшие элементы начинают выстраиваться с конца массива. То есть после первого шага самый большой по значению элемент массива будут стоять на последнем месте. Во втором шаге работа производится со всеми элементами кроме последнего. Опять находится самый большой элемент и ставится в конец массива, с которым производится работа. Третий шаг повторяет второй и так до тех пор, пока массив не будет отсортирован. Для более удобного восприятия приведу наглядный пример. Возьмем массив, состоящий из 7 элементов: 2,5,11,1,7,8,3. Смотрим.

Перейдем непосредственно к коду. Как уже было сказано нам необходимо два цикла. Вот как это будет выглядеть

const
m = 7; {колличетво элементов в массиве}

var
msort: array[1..m] of integer; {собственно наш массив}
i, j, k: integer; {i — это шаг ,j — это под-шаг}

begin
writeln(‘Введите элементы массива’);
for i := 1 to m do
read(msort[i]);

for i := 1 to m — 1 do
for j := 1 to m — i do
if msort[j] > msort[j + 1] then begin
k := msort[j];
msort[j] := msort[j + 1];
msort[j + 1] := k;
end;

write(‘Отсортированный массив: ‘);
for i := 1 to m do
write(msort[i]:4);

writeln;
end.

Обратите внимание на элемент k. Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).

15 комментариев

  • Рома

    Ответить 28.10.2011 02:06

    А почему метод сортировки пузырьком, называется методом сортировки пузырьком? 😀

  • Mr.Cheater

    Ответить 28.10.2011 22:07

    А почему паскаль назвали паскалем? Естественно, есть определенная причина) . Как и сортировка пузырьком.Кстати почему она названа именно так я объяснил в самой статье.

  • артём

    Ответить 18.01.2012 02:07

    почему в 20 строчке после операции пресваивания нету точки с запятой

  • Mr.Cheater

    Ответить 18.01.2012 15:09

    Странно . У меня , когда проверял ошибки не выдало . Сейчас проверил — та же история .
    Ошибку исправил , спасибо ,что сообщили.

  • GILL

    Ответить 20.01.2012 02:10

    Точка с запятой в данном случае необязательна. Это связано с тем, что знак «;» ставиться в случае разделения операторов. После выполнение оператора присваивания идёт закрывающаяся операторная скобка «end» — перед ней точку с запятой можно не ставить.

  • Mr.Cheater

    Ответить 06.02.2012 01:11

    Что Вы имеете в виду? Что некоторые элементы в массиве есть ,а некоторых еще нет? И необходимо заполнить оставшиеся элементы массива?

  • Programmer

    Ответить 06.02.2012 10:10

    А как заполнить массив, если уже в таблице(т.е. в массиве) уже даны числа? Как вывести формулу чтобы заполнить массив?

  • посторонний

    Ответить 23.03.2012 00:05

    Совет «Есть достаточно много различных методов, большинство из них не имеет широкой известности , да и знание их в принципе и не нужно » — замечательный. Так как раз и можно стать программистом.

    • Mr.Cheater

      Ответить 23.03.2012 02:12

      посторонний,
      Ну если Вы считаете ,что программистом можно стать изучая множество методов сортировки , из которых многие нерациональны да и медлительны по сравнению с другими , то ,наверное, у вас много лишнего времени и его некуда деть . В таком случае вы правы : хоть пользы и не будет,но вы хотя бы убьете время .

  • Евгений

    Ответить 22.05.2012 08:14

    25 строка (msort[i]:4)

    4 это сколько знаков идет типо?

  • Mr.Cheater

    Ответить 22.05.2012 21:14

    Евгений,
    Это сколько места отводится на одно число.
    в данном случае на одно число отводится 4 символа,включая пробелы.
    то есть если числа будут двухзначными,то на выводе будет
    41 52 64 75 89
    если трехзначными,то
    123 456 678 987 999
    а если четырехзначными,то мы не увидим пробелов между числами
    123423456345645675678907

  • Николай

    Ответить 26.09.2012 02:16

    у паскаля ест одно волшебное свойство, что можно писать процедуры и функции самому, и не писать их каждый раз по нескольку раз для сорта, модно просто прогонять невписанной процедурой и будет тебе счастье)

    • Mr.Cheater

      Ответить 27.09.2012 20:16

      Николай,
      ну это конечно можно, даже нужно, если в коде необходимо использовать сортировку несколько раз

  • алексей

    Ответить 22.12.2014 02:17

    а как сделать по убыванию ?

  • Светлана

    Ответить 07.03.2016 02:18

    Спасибо за описание метода пузырька. Хотелось бы поподробнее изучить метод Хоара. Что за метод выбора?

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