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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Пример, как методът на мехурчето сортира една редица. Елементите са представени като точки.

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

Принцип на действие[редактиране | edit source]

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

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

Производителност[редактиране | edit source]

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

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

Оптимизиране на метода на мехурчето[редактиране | edit source]

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

Зайци и костенурки[редактиране | edit source]

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

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

Пример стъпка по стъпка[редактиране | edit source]

Нека имаме масив със следните елементи: 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 )

В практиката[редактиране | edit source]

Въпреки че методът на мехурчето е един от най - простите алгоритми за сортиране за разбиране и имплементиране, неговата O(n2) сложност означава, че неговата ефикасност не е много голяма. Дори други O(n2) алгоритми за сортиране като например метода на пряката селекция са обикновено по - ефикасни.

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

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

Пример на C# за сортиране на числата, чрез алгоритъма на мехурчето[редактиране | edit source]

 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 за сортиране на числата, чрез алгоритъма на мехурчето[редактиране | edit source]

public class Mehurche {

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

Пример на C/C++ за сортиране на числата ,чрез алгоритъма на мехурчето[редактиране | edit source]

#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;
}

Вариации[редактиране | edit source]

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

Погрешно название[редактиране | edit source]

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

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