Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык 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.
Вот результат:
Оставить коментарий: