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

Методът е доста известен сред програмистите. Това е прост сортиращ алгоритъм, главната му употреба е въвеждане към останалите сортиращи алгоритми. Добър е за малки нишки, но за големи е доста неефективен.

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

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

Единственото значимо предимство, което има методът на мехурчето спрямо повечето други алгоритми за сортиране

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

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

 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] + " ");
        }
    }
}