Сортування бульбашкою

Матеріал з Вікіпедії — вільної енциклопедії.

Сортування бульбашкою
Основні відомості
Клас: Алгоритм сортування Структура даних: Масив Швидкодія: О(n²) Простір: О(n) загальний, O(1) допоміжний Оптимальний: Ні

Сортування обміном або Сортування бульбашкою є простим алгоритмом сортування. Алгоритм працює наступним чином — у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування згідно нього нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь.

[ред.] Аналіз

[ред.] Продуктивність

Складність алгоритму у найгіршому у середньостатистичному випадку рівна О(n²), де n — кількість елементів для сортування. Існує чимало значно ефективніших алгоритмів, наприклад, з найгіршою ефективністю рівною O(n log n). Тому даний алгоритм має низьку ефективність у випадках, коли N є досить великим, за винятком рідких конкретних випадків, коли заздалегідь відомо, що масив з самого початку буде добре відсотований.

[ред.] Кролики і черепахи

Позиція елементів, що підлягають сортуванню відіграє велику роль у питанні продуктивності даного алгоритму. Великі елементи на початку списку не являють проблеми, оскільки вони досить швидко переміщаються на свої місця. Однак, малі елементи у кінці списку переміщаються на його початок дуже повільно. Це призвело до того, що обидва типи елементів було названо кроликами і черепахами, відповідно.

З метою підвищення швидкодії алгоритму, у свій час було здійснено чимало зусиль для зменшення кількості "кроликів". Сортування перемішуванням є порівняно не поганим, однак, усе ще у своєму найгіршому випадку має складність O(n²). Сортування гребінцем спершу порівнює великі елементи один з одним, а вже тоді поступово переходить до все менших і менших. Його середньотатистична швидкість приблизно рівна такій в алгоритми Швидке сортування.

[ред.] Приклад реалізації крок за кроком

Візьмемо масив чисел "5 1 4 2 8", і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділені жирним шрифтом будуть порівнюватись.

Перший прохід:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями.
( 1 5 4 2 8 ) ( 1 4 5 2 8 )
( 1 4 5 2 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Тут порівнювані елементи знаходяться на своїх місцях, тож алгоритм не міняє їх місцями.
Другий прохід:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Тепер наш масив повністю відсортований, однак, алгоритм цього ще не знає. Йому потрібен ще один "пустий" прохід, під час якого від не поміняє місцями жодного елементу.
Третій прохід:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Нарешті, масив відсортовано, і алгоритм може припинити свою роботу.

[ред.] Реалізація на різних мовах програмування

[ред.] Псевдокод

function bubblesort (A : list[1..n]) {
    var int i, j;
    for i from n downto 1 {
        for j from 1 to i-1 { 
            if (A[j] > A[j+1])
                swap(A[j], A[j+1])
        }
    }
}

[ред.] Assembler

	mov	bx, offset array
	mov	cx, n
for_i:
        dec	cx
	xor	dx, dx
for_j:
	cmp	dx, cx
	jae	exit_for_j
	mov	si, dx
	mov	di, dx
	inc	di
	mov	al, byte ptr bx[si]
	cmp	al, byte ptr bx[di]
	jbe	no_swap 
	mov	ah, byte ptr bx[di]
	mov	byte ptr bx[di], al
	mov	byte ptr bx[si], ah 
no_swap:
	inc	dx
	jmp	for_j
exit_for_j:	
	loop	for_i

[ред.] GNU Assembler

.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

[ред.] C

#include <stdio.h>
#include <string.h>
 
 
int array[10] = {8, 6, 1, 3, 9, 4, 2, 7, 0, 5};
 
void swap (int a, int b)
{
    int c;
 
    c = array[a];
    array[a] = array[b];
    array[b] = c;
}
 
void print_array ()
{
    for (int i = 0; i < 10; i++)
        printf ("array[%d] = %d\n", i, array[i]);
}
 
int main ()
{
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < 9; j++) {
            if (array[j] > array[j + 1])
                swap (j, j + 1);
        }
    }	
 
    print_array();
 
    return (0);
}

[ред.] C++

#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

[ред.] C#

void BubbleSort(ref int[] a)
{
    for(int i = a.Length - 1 ; i > 0 ; i--)
        for(int j = 0 ; j < i ; j++)
	    if( a[j] > a[j+1] )
	    {
		int tmp = a[j];
		a[j] = a[j+1]; {{1}}
		a[j+1] = tmp;
	    }
}

[ред.] Fortran

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

[ред.] Java

void swap(int[] arr, int i, int j)
{
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
 
void bubblesort(int[] arr)
{
    for(int i = arr.length-1 ; i >= 0 ; i--)
        for(int j = 0 ; j < i ; j++)
            if( arr[j] > arr[j+1] )
                swap(arr, j, j+1);
}

[ред.] Pascal

for i:=n-1 downto 1 do {n - розмір масива arr[]}
    for j:=1 to i do
        if arr[j]>arr[j+1] then 
        begin
            tmp:= arr[j];
            arr[j]:= arr[j+1];
            arr[j+1]:= tmp;
        end;
write('вивід значень arr[]: ');
for i:=1 to n do
    write(arr[i],' ');
writeln();

[ред.] 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, j 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

[ред.] На практиці

Хоча, алгоритм є одним із найпростіших алгоритмів сортування, його ефективність є досить низькою, і він погано підходить для сортування великих списків. Більшість інших алгоритмів з такою ж швидкодією O(n²) є ефективнішими за алгоритм сортуванням бульбашками, наприклад, сортування включенням.

Через свою простоту, алгоритм часто використовується для пояснення студентам концепції алгоритмів, та алгоритмів сортування, зокрема. Однак, деякі дослідники, як то Оуен Астрахан (Owen Astrachan) ретельно дослідивши даний алгоритм, стверджують, що він настільки поганий і неефективний, що вони навіть не використовуватимуть його в якості прикладу у своїй викладацькій діяльності.^[1]

Дональд Кнут у своїй знаменитій праці The Art of Computer Programming прийшов до висновнку, що "немає жодних підстав рекомендувати використовувати даний алгоритм, окрім, хібащо через примітну назву і через те, що він є лідером у кількості цікавих теоретичних пробем", частину з яких він обговорює у своїй праці.

Сортування бульбашкою під час своєї роботи є асимптоматичним еквівалентом алгоритму сортування включенням, у своєму найгіршому випадку, однак, обидва алгоритми дуже сильно відрізняються кількістю необхідних операцій переміщення. Результати низки експериментів, наприклад, проведених Астраханом також підверджують той факт, що продуктивність алгоритму сортування включенням є значно вищою. Тому багато сучасних посібників з алгоритмів навіть не згадують про алгоритм сортування бульбашками, і віддають перевагу сортуванню включеннями.

Сортування бульбашкою також погано використовує можливості сучасних мікропроцесорів. Він вимагає щонайменше удвічі більше операцій, ніж сортування включенням, удвічі більше кеш пам'яті, і асимптоматично більше передбачень переходів. Результати експериментів проведених Астраханом показали, що сортування рядка за алгоритмом сортування бульбашками у п'ять разів повільніше за сортування того ж рядка за алгоритмом сортування включенням і на 40% повільніше за сортування за алгоритмом сортування вибором.^[2]

[ред.] Джерела інформації

1. ↑ http://www.cs.duke.edu/~ola/papers/bubble.pdf
2. ↑ Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003. (pdf)

• Дональд Кнут. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.38.
• Sorting in the Presence of Branch Prediction and Caches

[ред.] Зовнішні посилання

• Animated Sorting Algorithms: Bubble Sort – графічна демонстрація роботи алгоритму
• Bubble Sort Demo
• Bubble Sort Demonstration
• Lafore's Bubble Sort
• Sorting Applets in C++
• C++ Program - Bubble Sort
• Analyze Bubble Sort in an online Javascript IDE
• A colored graphical Java applet

п • о • р Алгоритми сортування Теорія Обчислювальна складність | Нотація великого О | Відношення порядку | Список | Стабільність | Сортування на основі порівнянь Сортування обміном Сортування бульбашкою | Сортування змішуванням | Odd-even sort | Сортування гребінцем | Сортування гнома | Швидке сортування Сортування вибором Сортування вибором | Пірамідальне сортування Сортування включенням Сортування включенням | Сортування Шелла | Сортування бінарним деревом | Сортування вставкою з проміжками | Patience sorting Сортування злиттям Сортування злиттям | Strand sort Алгоритми без порівнянь Сортування за розрядами | Сортування комірками | Сортування підрахунком | Цифрове сортування | Burstsort | Bead sort Інші Топологічне сортування | Sorting network | Bitonic sorter Непрактичні алгоритми Сортування Бого | Stooge sort