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

от Уикипедия, свободната енциклопедия
Jump to navigation Jump to search
Пример, как методът на мехурчето сортира една редица. Елементите са представени като точки.
Метод на мехурчето Променено цвят
Метод на мехурчето Променено цвят

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

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

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

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

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

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

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

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

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

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

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

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

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

Нека имаме масив със следните елементи: 5,1,4,2,8 и да го сортираме във възходящ ред като използваме метода на мехурчето. На всяка стъпка елементите, които са удебелени биват разменяни.
Първо преминаваме:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Тук алгоритъмът сравнява първите два елемента и ги разменя, тъй като 5 > 1
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Тук алгоритъмът сравнява вторият и третият елемент и ги разменя, тъй като 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Тук алгоритъмът сравнява третият и четвъртият елемент и ги разменя, тъй като 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Тук след като елементите са вече в ред (8 > 5), алгоритъмът няма нужда да ги разменя.
Второ преминаваме
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Тук нищо не разменя, защото първите два елемента са наредени 1 < 4
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Тук разменя вторият и третият елемент, тъй като 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 ), Тук нищо не разменя, защото третият и четвъртият елемент са наредени 4 > 5
( 1 2 4 5 8 ) ( 1 2 4 5 8 ), Тук отново не се разменя, защото последните два елемента са наредени 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 )

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

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

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

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

  1. 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)
  • В някои случаи, алгоритъмът за сортиране работи от дясно на ляво(обратната посока), което е по-удобно за частично сортирани колекции или колекции с несортирани елементи, добавени в края.

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

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

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