Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги.
image: пузырьки
Сегодня поговорим о простейших сортировках обменами .
Если кому интересно, скажу, что есть и другие классы – сортировки выбором , сортировки вставками , сортировки слиянием , сортировки распределением , гибридные сортировки и параллельные сортировки . Есть, кстати, ещё эзотерические сортировки . Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.
Но к сегодняшней лекции это не имеет отношения, нас сейчас интересуют только простенькие сортировки обменами. Самих сортировок обменами тоже немало (я знаю более дюжины), поэтому мы рассмотрим так называемую пузырьковую сортировку и некоторые другие, с ней тесно взаимосвязанные.
Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O (n 2 ). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте , в Википедии или где-нибудь ещё.
Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.
Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…
«Так любой дурак сортировать умеет» - скажете Вы и будете абсолютно правы. Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ. Сейчас у него временная сложность O (n 3 ), произведя одну коррекцию, мы уже доведём до O (n 2 ), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O (n log n ) – и это будет вовсе не «Быстрая сортировка»!
Внесём в глупую сортировку одно-единственное улучшение. Обнаружив при проходе два соседних неотсортированных элемента и поменяв их местами, не станем откатываться в начало массива, а невозмутимо продолжим его обход до самого конца.
В этом случае перед нами не что иное как всем известная…
Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…
Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.
Как видите, если к процессу перебора подойти творчески, то выталкивание тяжёлых (лёгких) элементов к концам массива происходит быстрее. Поэтому умельцы предложили для обхода списка ещё одну нестандартную «дорожную карту».
В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.
Разберём последнее покращення * для Сортування бульбашкою ** - Сортування гребінцем ***. Этот способ упорядочивает весьма шустро, O (n 2 ) – его наихудшая сложность. В среднем по времени имеем O (n log n ), а лучшая даже, не поверите, O (n ). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии. Впрочем, я обещал, что в крейсерские скорости мы сегодня углубляться не станем, засим умолкаю и перехожу непосредственно к алгоритму.
image: виноватая черепашка
Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения , оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.
Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения :
Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.
Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.
- Примечания
* покращення (укр.
) – улучшение
** Сортування бульбашкою (укр.
) – Сортировка пузырьком
*** Сортування гребінцем (укр.
) – Сортировка расчёской
Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке - это сортировка методом пузырька, которую также называют сортировкой простого обмена.
Для начала, что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива, начиная от минимального (максимального)" . Имейте ввиду, что это то же самое.
Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх.
var
msort: array 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 then begin
k:= msort[j];
msort[j] := msort;
msort := k;
end;
Write("Отсортированный массив: ");
for i:= 1 to m do
write(msort[i]:4);
end.
Обратите внимание на элемент k . Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:
После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:
Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево:
Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк):
Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки: Визуализация работы пузырьковой сортировки
toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов;
и, наконец, главный метод:
bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно:
public void bubbleSorter () { //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ for (int out = elems - 1 ; out >= 1 ; out-- ) { //Внешний цикл for (int in = 0 ; in < out; in++ ) { //Внутренний цикл if (a[ in] > a[ in + 1 ] ) //Если порядок элементов нарушен toSwap (in, in + 1 ) ; //вызвать метод, меняющий местами } } }На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке. Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов. Jgd!
Всем привет!
Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:
Алгоритм: Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет "вытолкнут" - и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.
Вернемся к нашему массиву:3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два - значит меняем местами: 1 3 2 4
. Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился - он всё равно, после прохождения циклом всего массива, будет последним. Аналогия - как пузырёк воздуха всплывает в воде - так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.
Теперь осталось запрограммировать данный алгоритм на языке Pascal.
const n = 4; {Заводим константу, это будет длина массива}
var i, j, k:integer; {Две переменные для вложенного цикла, одна для того чтобы элементы менять местами }
m:array 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 then begin
k:=m[j];
m[j]:=m;
m:=k;
end;
end;
end;
{Выводи результат:}
for i:=1 to n do
Write(m[i], " ");
end.
Вот результат:
Сортировка пузырьком – простейший алгоритм сортировки, применяемый чисто для учебных целей. Практического применения этому алгоритму нет, так как он не эффективен, особенно если необходимо отсортировать массив большого размера. К плюсам сортировки пузырьком относится простота реализации алгоритма.
Алгоритм сортировки пузырьком сводится к повторению проходов по элементам сортируемого массива. Проход по элементам массива выполняет внутренний цикл. За каждый проход сравниваются два соседних элемента, и если порядок неверный элементы меняются местами. Внешний цикл будет работать до тех пор, пока массив не будет отсортирован. Таким образом внешний цикл контролирует количество срабатываний внутреннего цикла Когда при очередном проходе по элементам массива не будет совершено ни одной перестановки, то массив будет считаться отсортированным. Чтобы хорошо понять алгоритм, отсортируем методом пузырька массив, к примеру, из 7 чисел (см. Таблица 1).
исходный массив: 3 3 7 1 2 5 0
№ итерации | Элементы массива | Перестановки | ||||||
---|---|---|---|---|---|---|---|---|
исх. массив | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
0 | 3 | 3 | false | |||||
1 | 3 | 7 | false | |||||
2 | 1 | 7 | 7>1, true | |||||
3 | 2 | 7 | 7>2, true | |||||
4 | 5 | 7 | 7>5, true | |||||
5 | 0 | 7 | 7>0, true | |||||
тек. массив | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
0 | 3 | 3 | false | |||||
1 | 1 | 3 | 3>1, true | |||||
2 | 2 | 3 | 3>2, true | |||||
3 | 0 | 3 | 3>0, true | |||||
4 | 3 | 5 | false | |||||
5 | 5 | 7 | false | |||||
тек. массив | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
0 | 1 | 3 | 3>1, true | |||||
1 | 2 | 3 | 3>2, true | |||||
2 | 0 | 3 | 3>0, true | |||||
3 | 3 | 3 | false | |||||
4 | 3 | 5 | false | |||||
5 | 5 | 7 | false | |||||
тек. массив | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
1 | 2 | false | ||||||
0 | 2 | 2>0, true | ||||||
2 | 3 | false | ||||||
3 | 3 | false | ||||||
3 | 5 | false | ||||||
5 | 7 | false | ||||||
тек. массив | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
0 | 1 | 1>0, true | ||||||
1 | 2 | false | ||||||
2 | 3 | false | ||||||
3 | 3 | false | ||||||
3 | 5 | false | ||||||
5 | 7 | false | ||||||
конечный массив | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
Конец сортировки |
Для того чтобы отсортировать массив хватило пяти запусков внутреннего цикла, for . Запустившись, цикл for срабатывал 6 раз, так как элементов в массиве 7, то итераций (повторений) цикла for должно быть на одно меньше. На каждой итерации сравниваются два соседних элемента массива. Если текущий элемент массива больше следующего, то меняем их местами. Таким образом, пока массив не будет отсортирован, будет запускаться внутренний цикл и выполняться операция сравнения. Обратите внимание на то, что за каждое полное выполнение цикла for как минимум один элемент массива находит своё место. В худшем случае, понадобится n-2 запуска внутреннего цикла, где n – количество элементов массива. Это говорит о том, что сортировка пузырьком крайне не эффективна для больших массивов.
Разработаем программу, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька.
// bu_sort.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include
Результат работы программы показан на рисунке 1.
Рисунок 1 — Сортировка пузырьком