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

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

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

Теперь подробнее о самом алгоритме. Все достаточно просто :
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 . Он нужен только для одной цели : чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие . Поэтому приходится расписывать ее самому , добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена , следующие статьи выйдут в течении следующей недели (а может и раньше).
Понравилась новость? Добавь в закладки!
Хочешь получать свежие новости? Подпишись на обновления с сайта!
Рекомендуем посмотреть:
#1 | написал: Рома | 28 октября 2011 12:05 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#2 | написал: Mr.Cheater | 28 октября 2011 14:13 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#3 | написал: артём | 18 января 2012 18:33 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#4 | написал: Mr.Cheater | 18 января 2012 21:20 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#5 | написал: GILL | 20 января 2012 21:51 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#6 | написал: Programmer | 6 февраля 2012 13:40 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#7 | написал: Mr.Cheater | 6 февраля 2012 15:04 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#8 | написал: посторонний | 23 марта 2012 20:39 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#9 | написал: Mr.Cheater | 23 марта 2012 22:09 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#10 | написал: Евгений | 22 мая 2012 19:30 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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

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


#11 | написал: Mr.Cheater | 22 мая 2012 20:26 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#12 | написал: Николай | 26 сентября 2012 23:50 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#13 | написал: Mr.Cheater | 27 сентября 2012 08:11 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#14 | написал: алексей | 22 декабря 2014 17:06 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
а как сделать по убыванию ?

#15 | написал: Светлана | 7 марта 2016 00:14 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Спасибо за описание метода пузырька. Хотелось бы поподробнее изучить метод Хоара. Что за метод выбора?

Добавление комментария

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Вставка исходного кода Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера

Введите два слова, показанных на изображении: