Метод пузырька c по убыванию. Сортировка пузырьком. Сортировка многомерного массива
Метод пузырька
Сортировка простыми обменами , сортиро́вка пузырько́м (англ. bubble sort ) - простой алгоритм сортировки . Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n ²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками .
Алгоритм
Пример сортировки пузырьком списка случайных чисел.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка .
Примеры реализации
Python
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
VBA
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
Усовершенствованный алгоритм сортировки пузырьком в Pascal
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 ;
PHP
$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 ; } }
Расположим массив сверху вниз, от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию...
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
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), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (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 Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
Второй проход:
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
Теперь массив отсортирован и алгоритм может быть завершён.
Реализация алгоритма на различных языках программирования:
Mov bx, offset array
mov cx, n
for_i:
dec cx
xor dx, dx
for_j:
cmp dx, cx
jae exit_for_j
jbe no_swap
mov ah, byte ptr bx
mov byte ptr bx, al
mov byte ptr bx, ah
no_swap:
inc dx
jmp for_j
exit_for_j:
loop for_i Text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
.type bubble_sort, @function
bubble_sort:
mov 8(%esp), %ecx # unsigned length
cmp $1, %ecx
jbe exit
mov 4(%esp), %eax # unsigned *array
dec %ecx
for_ecx:
xor %edi, %edi
for_edi:
mov (%eax,%edi,4), %ebx
cmp %ebx, 4(%eax,%edi,4)
jae no_xchng
mov 4(%eax,%edi,4), %edx
mov %edx, (%eax,%edi,4)
mov %ebx, 4(%eax,%edi,4)
no_xchng:
inc %edi
cmp %edi, %ecx
jne for_edi
loop for_ecx
exit:
ret
#define SWAP(A, B) { int t = A; A = B; B = t; }
void bubblesort(int *a, int n)
{
int i, j;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a)
SWAP(a[j], a);
}
}
}
#include Void bubble(int* a, int n)
{
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a)
{
int tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Void BubbleSort(int A)
{
for (int i = 0; i < A.Length; i++)
{
for (int j = i+1; j < A.Length; j++)
{
if (A[j] < A[i])
{
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
Сортировка одномерного динамического целочисленного массива: Type
TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
var i,p,n: Integer; b: boolean;
begin
n:= Length(a);
if n < 2 then exit;
repeat
b:= false;
Dec(n);
if n > 0 then
for i:= 0 to n-1 do
if a[i] > a then
begin
p:= a[i];
a[i]:= a;
a:= p;
b:= true;
end;
until not b;
end;
Void bubbleSort(alias op, T)(T inArray) {
foreach (i, ref a; inArray) {
foreach (ref b; inArray) {
if (mixin(op)) {
auto tmp = a;
a = b;
b = tmp;
}
}
}
}
Do i=n-1,1,-1
do j=1,i
if (a(j).gt.a(j+1)) then
t=a(j)
a(j)=a(j+1)
a(j+1)=t
endif
enddo
enddo
Void bubblesort(int arr) {
for (int i = 0; i < arr.length-1; i++){
for (int j = i+1; j < arr.length; j++){
if (arr[i] < arr[j]) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
}
For i:=n-1 downto 1 do {n - размер массива M}
for j:=1 to i do
if M[j]>M then
begin
tmp:= M[j];
M[j]:= M;
M:= tmp;
end;
write("вывод значений M: ");
for i:=1 to n do
write(M[i]:4);
writeln;
Усовершенствованный алгоритм сортировки пузырьком: P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
P:=false;
For i:=1 To n-k Do
If X[i] > X Then
Begin
A:=X[i];
X[i]:=X;
X:=A;
P:=true;
End;
k:=k+1;
End;
For(@out){
for(0..$N-1){
if($out[$_]gt$out[$_+1]){
($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
}
}
}
Arr =
swap = true
size = arr.length - 1
while swap
swap = false
for i in 0...size
swap |= arr[i] > arr
arr[i], arr = arr, arr[i] if arr[i] > arr
end
size -= 1
end
puts arr.join(" ")
# output => 1 3 3 5 8 10 11 12 17 20
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:
swap(arr, j, j + 1)
i -= 1
Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
t = False
For i = 0 To UBound(Mus()) - 1
If Mus(i) > Mus(i + 1) Then
tmp = Mus(i)
Mus(i) = Mus(i + 1)
Mus(i + 1) = tmp
t = True
End If
Next
Loop
End Sub
$size = sizeof($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;
}
}
Function sortBubble(data) {
var tmp;
for (var i = data.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (data[j] > data) {
tmp = data[j];
data[j] = data;
data = tmp;
}
}
}
return data;
}
Function bubbleSort(seq:Number):Number{
var sort = seq;
var elem:Number;
for(n in reverse ){
for(i in ){
if(sort < sort[i]){
elem = sort[i];
sort[i] = sort;
sort = elem;
}
}
}
return sort;
}
Using System.Console;
using Nemerle.Collections;
def arr = array ;
foreach (i in )
foreach (j in )
when (arr[j] > arr)
(arr[j], arr) = (arr, arr[j]);
WriteLine($"Sorted list is a $(arr.ToList())");
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 " 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] "FRE(-1)=21440-21456
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
FOR X = 1 TO N
Y[X] = X
PRINT Y[X];
NEXT X:PRINT
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
PRINT " SLUCHAINYE CHISLA"
FOR X = 1 TO N
YD=Y[X]
XS=INT(RND*N)+1
PRINT XS;
Y[X]=Y
Y=YD
NEXT X:PRINT
PRINT " PEREMESHANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
"ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
F=0
FOR I=1 TO N-J STEP 1
"IF Y[I] > Y THEN D=Y[I]:Y[I]=Y:Y=D:F=1
IF Y[I] > Y THEN SWAP Y[I],Y:F=1
LOCATE 8,1 REM
PRINT " ANYMACIJA SORTIROVKI" REM
FOR X1=1 TO N REM ANIMATION BLOCK
PRINT Y; REM
NEXT X1:PRINT REM
DELAY .5 REM
NEXT I
IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
PRINT " OTSORTIROVANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
При написании статьи были использованы открытые источники сети интернет:
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Вам, в отличие от компьютерной программы сортировка не составит никого труда, ведь вы способны видеть картину в целом и сразу сможете прикинуть, какого героя, куда нужно переместить, чтобы сортировка по росту была выполнена успешно. Вы уже наверняка догадались, что для сортировки по возрастанию этой структуры данных достаточно поменять местами Халка и Железного человека:
После того, как вы пройдете с таким алгоритмом по всему списку за один проход, сортировка будет произведена не полностью. Но зато, самый большой элемент в списке будет перемещен в крайнюю правую позицию. Это будет происходить всегда, ведь как только вы найдете самый большой элемент, вы все время будете менять его местами пока не переместите в самый конец. То есть, как только программа «найдет» Халка в массиве, она будет двигать его дальше в самый конец списка:
Именно поэтому этот алгоритм называется пузырьковой сортировкой, так как в результате его работы самый большой элемент в списке оказывается в самом верху массива, а все более мелкие элементы будут смещены на одну позицию влево:
Чтобы завершить сортировку нужно будет вернуться к началу массива и повторить описанные выше пять шагов еще раз, снова перемещаясь слева направо, сравнивая и по необходимости перемещая элементы. Но на этот раз вам нужно остановить алгоритм за один элемент до конца массива, ведь мы уже знаем, что в крайней правой позиции абсолютно точно находится самый большой элемент (Халк):
Таким образом, программа должна иметь два цикла. Для большей наглядности, перед тем как мы перейдем к рассмотрению программного кода, по этой ссылке можно ознакомиться с визуализацией работы пузырьковой сортировки:
Визуализация работы пузырьковой сортировки
toSwap – переставляет местами элементы в случае необходимости. Для этого используется временная переменная dummy , в которую записывается значение первого числа, а на место первого записывается значение из второго числа. После этого содержимое из временной переменной записывается во второе число. Это стандартный прием перестановки местами двух элементов; и, наконец, главный метод: bubbleSorter – который производит основную работу и сортирует данные, хранящиеся в массиве, еще раз приведем его отдельно: На скорость алгоритма влияет не только количество проходов, но и количество перестановок, которые потребуется совершить. Для случайных данных количество перестановок в среднем составляет (N^2) / 4, то есть примерно в половину меньше, чем количество проходов. Однако, в худшем случае количество перестановок также может составить N^2 / 2 – это в том случае, если данные изначально отсортированы в обратном порядке.
Не смотря на то, что это достаточно медленный алгоритм сортировки, знать и понимать как он работает довольно важно, к тому же, как было сказано ранее, он является основой для более сложных алгоритмов.
Jgd!Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Худшее время
Лучшее время
Среднее время
Затраты памяти
Пример работы алгоритма
Синтаксис Intel
Синтаксис AT&T (GNU)
C
C++
С использованием Template
Без использования Template
C#
Delphi
D
Fortran
Java
Pascal
Perl
Ruby
Python
VBA
PHP
JavaScript
JavaFX
Nemerle
TurboBasic 1.1
Введение
Весь современный интернет представляет из себя огромное количество разнотипных структур данных, собранных в базы данных. В них хранится всевозможная информация, начиная от личных данных пользователей и заканчивая семантическим ядром высокоинтеллектуальных автоматизированных системами. Стоит-ли говорить о том, что сортировка данных играет крайне важную роль в этом огромном количестве структурированной информации. Сортировка может стать обязательным шагом перед поиском какой-либо информации в базе, и знание алгоритмов сортировки играет крайне важную роль в программировании.
Существует довольно большое количество алгоритмов сортировки, многие из них весьма специфические и разрабатывались для решения узкого круга задач и работы с конкретными типами данных. Но среди всего этого многообразия самым простейшим алгоритмом заслуженно является пузырьковая сортировка
, которую можно реализовать на любом языке программирования. Несмотря на свою простоту, она лежит в основе многих довольно сложных алгоритмов. Другим ее не менее важным достоинством является ее простота, а, следовательно, ее можно вспомнить и реализовать сходу, не имея перед глазами какой-либо дополнительной литературы.
Сортировка глазами машины и глазами человека
Давайте представим, что вам нужно отсортировать по возрастанию 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. Таким образом, с увеличением количества элементов сложность сортировки значительно увеличивается:
