Алгоритм сортировки одномерного массива методом «пузырька». Описание алгоритма. Блок-схема и программа сортировки по возрастанию массива типа real из 7 элементов.
Описание алгоритма
Классификация методов сортировки не всегда четко определена. Остановимся на методе, в котором обмен двух элементов является основной характеристикой процесса. Приведенный ниже алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы.
Как и в предыдущих методах простого выбора, мы совершаем повторные проходы по массиву, каждый раз просеивая наименьший элемент оставшегося множества, двигаясь к левому концу массива. Если, для разнообразия, мы будем рассматривать массив, расположенный вертикально, а не горизонтально и – при помощи некоторого воображения - представим себе элементы пузырьками в резервуаре с водой, обладающими «весами», соответствующими их ключам, то каждый проход по массиву приводит к «всплыванию» пузырька на соответствующий его весу уровень (см. табл. 2). Этот метод широко известен как сортировка методом пузырька . Его простейший вариант приведен в программе 1.
procedure bubblesort ;
var i , j : index ; x : item ;
begin for i := 2 to n do
begin for j := n downto i do
if a [j -1].key > a [j ].key then
begin x := a [j -1]; a [j -1] := a [j ]; a [j ] := x
end {bubblesort }
Этот алгоритм легко оптимизировать. Пример в табл. 2 показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм – это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса k , уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться до установленной заранее нижней границыi . Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывает на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив
12 18 42 44 55 67 94 06
будет рассортирован при помощи метода пузырька за один проход, а сортировка массива
94 06 12 18 42 44 55 67
потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов.
Анализ сортировки методом пузырька.
Число сравнений в алгоритме простого обмена равно
,
минимальное, среднее и максимальное количества пересылок (присваиваний элементов) равны
,
,
.
Программа сортировки
A: array of real;
N, j, k: integer;
WriteLn("Ввод массива");
for j:= 1 to N do
Write("A", j, "=");
WriteLn("Исходный массив");
for j:= 1 to N do
Write(A[j]:8:1);
for j:= 2 to k do
if A > A[j] then
A := A[j];
WriteLn("Отсортированный массив");
for j:= 1 to N do
Write(A[j]:8:1);
Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке - это сортировка методом пузырька, которую также называют сортировкой простого обмена.
Для начала, что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива, начиная от минимального (максимального)" . Имейте ввиду, что это то же самое.
Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх.
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 . Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).
Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги.
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 году Стивен Лейси и Ричард Бокс.
Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.
- Примечания
* покращення (укр.
) – улучшение
** Сортування бульбашкою (укр.
) – Сортировка пузырьком
*** Сортування гребінцем (укр.
) – Сортировка расчёской
Расположим массив сверху вниз, от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию...
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Template
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n 2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит?
Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала!).
Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой ".
Template
Насколько описанные изменения повлияли на эффективность метода? Среднее количество сравнений, хоть и уменьшилось, но остается O(n 2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:
После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:
Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево:
Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк):
Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки: Визуализация работы пузырьковой сортировки
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!