Пузырьковая сортировка и все-все-все. Сортировка пузырьком
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания . Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).
Решение
Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька , который также называют методом простого обмена . В чем же он заключается, и почему у него такое странное название: "метод пузырька"?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм и особенности этой сортировки таковы:
- При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
- Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
- При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
- На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
- В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
- После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
- Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
- При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.
Программа на языке Паскаль:
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 .
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (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 var begin For i:= 1 to m - 1 do Write("Отсортированный массив: "); end. Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:
После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:
Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево:
Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк):
Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки:
Визуализация работы пузырьковой сортировки
toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов; и, наконец, главный метод: bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно: На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке.
Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов.
Jgd! Всем привет! Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык 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.
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Сегодня мы затронем тему сортировки в Паскале. Есть достаточно много различных методов, большинство из них не имеет широкой известности, да и знание их в принципе и не нужно. Достаточно знать базовый набор и несколько дополнительных. В этой статья я расскажу вам о самой известной сортировке - это сортировка методом пузырька, которую также называют сортировкой простого обмена.
Для начала, что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива, начиная от минимального (максимального)" . Имейте ввиду, что это то же самое.
Вернемся к сортировке пузырьком. Почему ее назвали именно так? Дело в том, что это аналогия. Представьте себе обычный массив, расположенный вертикально. В результате сортировки более меньшие элементы поднимаются вверх. То есть здесь массив можно представить в виде воды, а меньшие элементы в виде пузырька, которые всплывают наверх. 
Теперь подробнее о самом алгоритме. Все достаточно просто:
1. Для сортировки используется 2 цикла, один вложен в другой. Один используется на шаги, другой на под-шаги.
2. Суть алгоритма - это сравнение двух элементов. Именно двух. Поясняю, например имеем массив с 10-ю элементами. Элементы будут сравниваться парами: 1 и 2, 2и 3,3 и 4,4 и 5,6 и 7 и т.д. При сравнении пар, если предыдущий элемент оказался больше чем последующий - то их меняют местами. Например если второй элемент равен 5 , а третий 2 , то они их поменяют местами.
3. Сортировка методом пузырька делится на шаги. В каждом шаге выполняется попарное сравнение. В результате каждого шага наибольшие элементы начинают выстраиваться с конца массива. То есть после первого шага самый большой по значению элемент массива будут стоять на последнем месте. Во втором шаге работа производится со всеми элементами кроме последнего. Опять находится самый большой элемент и ставится в конец массива, с которым производится работа. Третий шаг повторяет второй и так до тех пор, пока массив не будет отсортирован. Для более удобного восприятия приведу нагядный пример. Возьмем массив, состоящий из 7 элементов: 2,5,11,1,7,8,3. Смотрим.(Кликните на картинку для увеличения изображения)
Перейдем непосредственно к коду. Как уже было сказано нам необходимо два цикла. Вот как это будет выглядеть
const
m = 7; {колличетво элементов в массиве}
msort: array of integer; {собственно наш массив}
i, j, k: integer; {i - это шаг,j - это под-шаг}
writeln("Введите элементы массива");
for i:= 1 to m do
read(msort[i]);
for j:= 1 to m - i do
if msort[j] > msort then begin
k:= msort[j];
msort[j] := msort;
msort := k;
end;
for i:= 1 to m do
write(msort[i]:4);
Обратите внимание на элемент k . Он нужен только для одной цели: чтобы поменять два элемента массива местами. Дело в том, что в Паскале нет специальной функции, которая бы выполняла такое действие. Поэтому приходится расписывать ее самому, добавляя дополнительный элемент для обмена. На этом статья сортировка методом пузырька закончена, следующие статьи выйдут в течении следующей недели (а может и раньше).Введение
Весь современный интернет представляет из себя огромное количество разнотипных структур данных, собранных в базы данных. В них хранится всевозможная информация, начиная от личных данных пользователей и заканчивая семантическим ядром высокоинтеллектуальных автоматизированных системами. Стоит-ли говорить о том, что сортировка данных играет крайне важную роль в этом огромном количестве структурированной информации. Сортировка может стать обязательным шагом перед поиском какой-либо информации в базе, и знание алгоритмов сортировки играет крайне важную роль в программировании.
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка
, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Сортировка глазами машины и глазами человека
Давайте представим, что вам нужно отсортировать по возрастанию 5 столбиков разной высоты. Под этими столбиками может пониматься какая угодно информация (цены на акции, пропускная способность канала связи и пр.), можете представить какой-то свой вариант этой задачи, чтобы было более наглядно. Ну а мы, в качестве примера, будем сортировать мстителей по росту:
Done!
И на этом сортировка будет успешно завершена. Однако, вычислительная машина в отличие от вас несколько туповата не видит всю структуру данных целиком. Ее программа управления может сравнивать лишь два значения в один промежуток времени. Для решения этой задачи ей продеться помесить в свою память два числа и выполнить над ними операцию сравнения, после чего перейти к другой паре чисел, а так до тех пор, пока не будут проанализированы все данные. Поэтому любой алгоритм сортировки очень упрощенно можно представить виде трех шагов:
Разные алгоритмы могут по-разному выполнять эти операции, ну а мы перейдем к рассмотрению принципа работы пузырьковой сортировки.
Алгоритм пузырьковой сортировки
Пузырьковая сортировка считается самой простой, но перед тем как описывать этот алгоритм давайте представим, как бы вы отсортировали мстителей по росту, если бы могли, как и машина сравнивать между собой лишь двух героев в один промежуток времени. Скорее всего, вы бы поступили (самым оптимальным) следующим образом:
Реализация пузырьковой сортировки на языке Java
Для демонстрации работы сортировки на Java, приведем программный код, который:
Здесь следует обратить внимание на два счетчика: внешний out , и внутренний in .
Внешний счетчик out
начинает перебор значений с конца массива и постепенно уменьшается с каждым новым проходом на единицу. Переменная out с каждым новым проходом смещается все левее, чтобы не затрагивать значения, уже отсортированные в правую часть массива.
Внутренний счетчик in
начинает перебор значений с начала массива и постепенно увеличивается на единицу на каждом новом проходе. Увеличение in происходит до тех пока, пока он не достигнет out (последнего анализируемого элемента в текущем проходе). Внутренний цикл in производит сравнение двух соседних ячеек in и in+1 . Если в in хранится большее число, чем в in+1 , то вызывается метод toSwap , который меняет местами эти два числа.
Заключение
Алгоритм пузырьковой сортировки является одним из самых медленных. Если массив состоит из N элементов, то на первом проходе будет выполнено N-1 сравнений, на втором N-2, далее N-3 и т.д. То есть всего будет произведено проходов:
(N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2
Таким образом, при сортировке алгоритм выполняет около 0.5х(N^2) сравнений. Для N = 5 , количество сравнений будет примерно 10, для N = 10 количество сравнений вырастит до 45. Таким образом, с увеличением количества элементов сложность сортировки значительно увеличивается:
Плюсы:
Минусы:
Пусть есть у нас некий массив:
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
. Второй цикл закончили. Мы сделали уже два цикла - значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй - видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.
Вот результат:
А вот видеоурок