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

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

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

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

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

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

  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 Replies to “Сортировка методом пузырька”

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавить комментарий для Mr.Cheater Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *