Усовершенствованный пузырек c. Реализация пузырьковой сортировки на Java. С использованием Template
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (Selection sort)
Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i
Пузырьковая сортировка (Bubble sort)
При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.
Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i Всем привет! Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы. Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен: Алгоритм:
Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет "вытолкнут" - и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.
Вернемся к нашему массиву:3 1 4 2
Теперь осталось запрограммировать данный алгоритм на языке 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.
Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги. 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), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным. Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество. На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется. При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания
. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему). Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька
, который также называют методом простого обмена
. В чем же он заключается, и почему у него такое странное название: "метод пузырька"? Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива). Программа на языке Паскаль: const
m =
10
;
var
arr:
array
[
1
..
m
]
of
integer
;
i,
j,
k:
integer
;
begin
randomize;
write
("Исходный массив: "
)
;
for
i :
=
1
to
m do
begin
arr[
i]
:
=
random(256
)
;
write
(arr[
i]
:
4
)
;
end
;
writeln
;
writeln
;
for
i :
=
1
to
m-
1
do
for
j :
=
1
to
m-
i do
if
arr[
j]
> arr[
j+
1
]
then
begin
k :
=
arr[
j]
;
arr[
j]
:
=
arr[
j+
1
]
;
arr[
j+
1
]
:
=
k
end
;
write
("Отсортированный массив: "
)
;
for
i :
=
1
to
m do
write
(arr[
i]
:
4
)
;
writeln
;
readln
end
.
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Плюсы:
Минусы:
Пусть есть у нас некий массив:
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
. Второй цикл закончили. Мы сделали уже два цикла - значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй - видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.
Вот результат:
А вот видеоурок
Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка
. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort
, а про другой обменный способ – старую добрую пузырьковую сортировку
и её улучшения, модификации, мутации и разновидности. Глупая сортировка
Сортировка и впрямь глупейшая. Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы встретим пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся на круги своя, то бишь в самое начало. Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё сызнова. Продолжаем до тех пор пока массив потихоньку-полегоньку не отсортируется.Пузырьковая сортировка
Или сортировка простыми обменами
. Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.Шейкерная сортировка
Она же сортировка перемешиванием
, она же коктейльная сортировка
. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 180 0 и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.Чётно-нечётная сортировка
На сей раз мы не будем сновать по массиву взад-вперёд, а снова вернёмся к идее планомерного обхода слева-направо, но только сделаем шире шаг. На первом проходе элементы с нечётным ключом сравниваем с соседями, зиждущимися на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5-й с 6-м и так далее). Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.
Во всём виноваты черепашки
Небольшая предыстория. В 1980 году Влодзимеж Добосиевич пояснил почему пузырьковая и производные от неё сортировки работают так медленно. Это всё из-за черепашек
. «Черепахи» - небольшие по значению элементы, которые находятся в конце списка. Как Вы, возможно, заметили пузырьковые сортировки ориентированы на «кроликов» (не путать с «кроликами» Бабушкина) – больших по значению элементов в начале списка. Они весьма резво перемещаются к финишу. А вот медлительные пресмыкающиеся на старт ползут неохотно. Подгонять «тортилл» можно с помощью расчёски
. Сортировка расчёской
В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.
** Сортування бульбашкою (укр.
) – Сортировка пузырьком
*** Сортування гребінцем (укр.
) – Сортировка расчёской
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.Решение
Алгоритм и особенности этой сортировки таковы: