Сортировка пузырьком c. Сортировка методом пузырька. Сортировка глазами машины и глазами человека
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (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 Расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию. 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
.
Метод пузырька
Сортировка простыми обменами
, сортиро́вка пузырько́м
(англ. bubble sort
) - простой алгоритм сортировки . Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n
²). Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками . Пример сортировки пузырьком списка случайных чисел. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка . Def
swap(arr, i, j)
:
arr[
i]
, arr[
j]
= arr[
j]
, arr[
i]
def
bubble_sort(arr)
:
i = len
(arr)
while
i > 1
:
for
j in
xrange
(i - 1
)
:
if
arr[
j]
> arr[
j + 1
]
:
swap(arr, j, j + 1
)
i -= 1
Sub
Sort(Mus()
As
Long
)
Dim
n As
Long
, i As
Long
, tmp As
Long
i = 1
Do
While
(i < UBound
(Mus)
)
If
Mus(i)
> Mus(i + 1
)
Then
tmp = Mus(i)
Mus(i)
= Mus(i + 1
)
Mus(i + 1
)
= tmp
If
i > 1
Then
i = i - 1
Else
i = i + 1
End
If
Else
i = i + 1
End
If
Loop
End
Sub
P:=True
; {Перестановка есть}
K:=1
; {Номер просмотра}
While
P Do
Begin
P:=false
;
For
i:=1
To
n-k Do
If
X[
i]
> X[
i+1
]
Then
Begin
A:=X[
i]
;
X[
i]
:=X[
i+1
]
;
X[
i+1
]
:=A;
P:=true
;
End
;
k:=k+1
;
End
; $size
= count
($arr
)
-1
;
for
($i
= $size
; $i
>=0
; $i
--)
{
for
($j
= 0
; $j
<=($i
-1
)
; $j
++)
if
($arr
[
$j
]
>$arr
[
$j
+1
]
)
{
$k
= $arr
[
$j
]
;
$arr
[
$j
]
= $arr
[
$j
+1
]
;
$arr
[
$j
+1
]
= $k
;
}
}
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.Решение
Алгоритм и особенности этой сортировки таковы:
Алгоритм
Примеры реализации
Python
VBA
Усовершенствованный алгоритм сортировки пузырьком в Pascal
PHP