Категории:
Свежие
комментарии:
Полина:
Мы такие задачи решаем в 6 классе. Как раз вчера по инф..
Олег:
Спасибо, все очень подробно написано..
Калужский Александр:
Можете мне заказать.
Сортировка пузырьком (Pascal)
Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка — это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:
Плюсы:
- Простота реализации алгоритма
- Красивое название
Минусы:
- Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2 )
- Почти не применяется в реальной жизни (используется в основном в учебных целях)
Пусть есть у нас некий массив: 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.
Вот результат: 
А вот видеоурок
Презентация к уроку "Сортировка массивов. Метод Пузырька". 10 класс
Просмотр содержимого документа
«Сортировка массивов. Метод Пузырька»
Учитель Гоголев Д.Г.
Зачем нужна сортировка?
С отсортированными данными работать легче, чем с произвольно расположенными:
12 1 45 102 45 56 23 84 65 98 15 14 65 42 61 7 18 96 2 83 91
1 2 7 12 14 15 18 23 42 45 45 56 61 65 65 83 84 91 96 98 102
- когда элементы отсортированы, их проще найти;
- легче определить, имеются ли пропущенные элементы;
- проще удостовериться, что все элементы были проверены;
- легче найти общие элементы двух массивов.
Рассмотрим исходный массив:
Выбираем первый элемент: 9 .
Сравниваем его с остальными элементами массива, если находим меньший, то меняем их метами:
< 9 , 3 , 6, 0, 2 > < 3 , 9, 6, 0 , 2> < , 9, 6, 3, 2>
Выбираем второй элемент: 9 .
Сравниваем его с остальными элементами массива, если находим меньший, то меняем их метами:
Выбираем третий элемент: 9 .
Сравниваем его с остальными элементами массива, если находим меньший, то меняем их метами:
Выбираем четвертый элемент: 9 .
a[j] then begin c:=a[i]; a[i]:=a[j]; a[j]:=c; end; " width="640"
Реализация сортировки «пузырьком» на языке Pascal (одномерный массив)
Задача
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).
Решение
Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
