Метод на мехурчето

Пример, как методът на мехурчето сортира една редица. Елементите са представени като точки.

Метод на мехурчето (на английски: Bubblesort) е един от популярните и най-тривиални алгоритми за сортиране. Този алгоритъм за сортиране не е много ефективен, но е лесен за разбиране и съставяне.

Принцип на действие

Алгоритъмът работи по следния начин: взимаме първият елемент на масива и го сравняваме със следващия (втория в нашия случай) и разменяме стойностите им, ако първият е по – голям от втория. След това сравняваме вторият елемент с третия и пак разменяме, ако има нужда. Ако нашият масив е от 10 елемента, след 9 такива сравнения най – отгоре ще изплува най – голямата стойност. След това започваме отново да сравняваме като пак взимаме първият елемент и сравняваме с втория и така нататък.

В най-добрия случай методът на мехурчето има сложност Ω(n). Ако масивът е вече сортиран, методът на мехурчето ще премине през масива веднъж и ще установи, че не трябва да разменя никакви елементи.

Производителност

В най – лошия и среден случай методът на мехурчето има сложност О(n²), където n е броят на елементите, които биват сортирани. Съществуват много други алгоритми за сортиране, които имат сложност O(n log n). Дори и методът на пряката селекция, който има сложност като на метода на мехурчето, е с по – добра производителност. Следователно методът на мехурчето, не е добър избор, ако искаме да сортираме много на брой елементи.

Единственото значимо предимство, което има методът на мехурчето спрямо повечето други алгоритми за сортиране – дори и бързият алгоритъм(quicksort), но не и методът на пряката селекция(insertion sort), е че способността му да разбира кога масивът е сортиран, е ефикасно построена в алгоритъма. Производителността на метода на мехурчето спрямо вече сортиран масив е (най-добър случай) е O(n). За справка, повечето други алгоритми за сортиране, дори тези, които имат по – добра производителност в средния случай им отнема повече итерации. Обаче методът на пряката селекция извършва дори по – малко итерации от метода на мехурчето при сортиран масив. Метода на мехурчето не се препоръча да се ползва в случай на големи колекции.

Оптимизиране на метода на мехурчето

Методът на мехурчето може лесно да се оптимизира като наблюдаваме, че n-та итерация намира n-то най – голямо число и го слага на последно място. Затова вътрешният цикъл може да пропусне да проверява в последните n – 1 елементи когато минава за n-ти път.

Зайци и костенурки

Позицията на елементите в метода на мехурчето играе важна роля при определянето на неговата производителност. Големи елементи в началото на колекцията не представляват проблем, защото бързо се разменят. Но малки елементи в края на колекцията изключително бавно се придвижват към началото на колекцията. Това води до наименованието им – зайци и костенурки.

Различни усилия са били направени за да се реши този проблем. Методът на коктейла (cocktail sort) e двупосочен метод на мехурчето, който минава от началото до края, и след това се връща. Може да придвижва костенурките сравнително добре, но сложността на алгоритъма остава O(n²) в най-лошия случай.

Пример стъпка по стъпка

Нека имаме масив със следните елементи: 5,1,4,2,8 и да го сортираме във възходящ ред като използваме метода на мехурчето. На всяка стъпка елементите, които са удебелени биват разменяни.
Първо преминаваме:
(5 1 4 2 8) $\to$ (1 5 4 2 8), Тук алгоритъмът сравнява първите два елемента и ги разменя, тъй като 5 > 1
(1 5 4 2 8) $\to$ (1 4 5 2 8), Тук алгоритъмът сравнява вторият и третият елемент и ги разменя, тъй като 5 > 4
(1 4 5 2 8) $\to$ (1 4 2 5 8), Тук алгоритъмът сравнява третият и четвъртият елемент и ги разменя, тъй като 5 > 2
(1 4 2 5 8) $\to$ (1 4 2 5 8), Тук след като елементите са вече в ред (8 > 5), алгоритъмът няма нужда да ги разменя.
Второ преминаваме
(1 4 2 5 8) $\to$ (1 4 2 5 8), Тук нищо не разменя, защото първите два елемента са наредени 1 < 4
(1 4 2 5 8) $\to$ (1 2 4 5 8), Тук разменя вторият и третият елемент, тъй като 4 > 2
(1 2 4 5 8) $\to$ (1 2 4 5 8), Тук нищо не разменя, защото третият и четвъртият елемент са наредени 4 > 5
(1 2 4 5 8) $\to$ (1 2 4 5 8), Тук отново не се разменя, защото последните два елемента са наредени 5 < 8
Сега, масивът е вече сортиран, но нашият алгоритъм не знаеш дали е готов. Алгоритъмът трябва да направи още едно преминаваме, което е напълно излишно за да разбере, че масивът е сортиран
Трето преминаваме
(1 2 4 5 8) $\to$ (1 2 4 5 8)
(1 2 4 5 8) $\to$ (1 2 4 5 8)
(1 2 4 5 8) $\to$ (1 2 4 5 8)
(1 2 4 5 8) $\to$ (1 2 4 5 8)

В практиката

Поради своята простота, метода на мехурчето е често използван за да се въведе концепцията за алгоритъм или алгоритъм за сортиране на студентите. Въпреки това, някои изследователи като Оуен Астрахан са опитали да омаловажат метода на мехурчето и неговата популярност в компютърното образование, като предлагат повече да не бъде изучаван.

В Жаргоновия файл метода на мехурчето е още наричан лош алгоритъм. Доналд Кнут заявява в неговата книга „Изкуството на компютърното програмиране“, че методът на мехурчето няма какво да предложи, освен хващащо окото име и че води до някои интересни теоретични проблеми. Въпреки че методът на мехурчето е един от най – простите алгоритми за сортиране за разбиране и имплементиране, неговата O(n²) сложност означава, че неговата ефикасност не е много голяма. Дори други O(n²) алгоритми за сортиране като например метода на пряката селекция са обикновено по – ефикасни.

Пример на C# за сортиране на числата, чрез алгоритъма на мехурчето

 using System;
class BubbleSort
{
    static void Main()
    {
        int[] array = new int[] { 6, 9, 4, 3, 5, 1, 42, -2 };
        for (int i = 0; i < array.Length - 1; i++)
        {
            for (int j = 0; j < array.Length - 1; j++)
            {
                if (array[j] > array[j + 1]) // swap the elements
                {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
        for (int i = 0; i < array.Length; i++) // print the elements
        {
            Console.Write(array[i] + " ");
        }
    }
}

Пример на Java за сортиране на числата, чрез алгоритъма на мехурчето

public class Mehurche {

    public static void main(String[] args) {
		
	int[] array = new int[]{6,5,4,3,5,1,42,-1};
	for (int i = 0; i < array.length - 1; i++){
            for (int j = 0; j < array.length - 1; j++){
                if (array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
        for (int i = 0; i < array.length; i++){
            System.out.print(" " + array[i]);
        }	
    }
}

Пример на C/C++ за сортиране на числата, чрез алгоритъма на мехурчето

include <stdio.h>

int main(void) {

       int item[100];
       int a, b, t;
       int count;

       /*Прочитане на числата*/
       printf(„how many numbers?“);
       scanf(„%d“, &count);
       for(a=0; a<count; a++) scanf("%d", &item[a]);

       /*Сортиране чрез метода на мехурчето*/
       for(a=0; a<count; ++a)
       for(b=count-1; b>a; --b){

               /*Сравняване на съседни елементи*/
               if(item[b-1] > item[b]){
                       t = item[b-1];
                       item[b-1] = item[b];
                       item[b] = t;
               }
       }

       /*Изписване на числата*/
       for(t=0; t<count; t++) printf("chisloto e %d\n", item[t]);
       return 0;

}

Пример за сортиране на числа в лист по метода на мехурчето на Python 3

list1 = [10, 500, 100, 90, 65, 88, 11]

elements = len(list1)

swap = 0

for i in (list1):

   for i1 in range (elements – 1):

       if (list1[i1] > list1[i1 + 1]):

          swap = list1[i1]

           list1[i1] = list1[i1 + 1]

           list1[i1 + 1] = swap

for pr in list1:

   print (pr)

Вариации

Нечетен – четен алгоритъм за сортиране (odd-even sort)
Алгоритъм на коктейла (cocktail sort)
В някои случаи, алгоритъмът за сортиране работи от дясно наляво (обратната посока), което е по-удобно за частично сортирани колекции или колекции с несортирани елементи, добавени в края.

Погрешно название

Метода на мехурчето е често грешно назоваван „потъващият алгоритъм“. Потъващият алгоритъм е правилното название на метода на вмъкване. Грешката се поражда от Националния Институт по Стандарти и Технологии, който казва, че „потъващият алгоритъм“ е синоним на метода на мехурчето

За да изясним, можем да наблюдаваме поведението на двата алгоритъма. При метода на мехурчето, по-големите балончета (по-големите стойности) се изкачват като взимат местата на по-малките балончета (по-малките стойности). От друга страна, при метода на вмъкване всеки успешен елемент потъва до неговата правилна позиция в сортираната част на масива.