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

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

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

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

Алгоритъмът сравнява последователно всички двойки съседни елементи a_i-1 и а_i, и ако a_i-1>a_i местата им биват разменени. Методът може да се използва в програми, които трябва да подредят масив по даден критерий. a₁ a₃ a₅ a₂ a₄ => a₁ a₂ a₃ a₄ a₅.

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

Пример

Ако несортираният масив има вид: 5 1 4 2 8 и искаме да получим елементите, сортирани във възходящ ред:

• Вземат се първите два елемента от масива: 5 и 1
• Тъй като 1 < 5 се разменят местата им. Текущ масив: 1 5 4 2 8
• Вземат се следващите два елемента от масива: 5 и 4
• Тъй като 4 < 5 се разменят местата им. Текущ масив: 1 4 5 2 8
• Вземат се следващите два елемента от масива: 5 и 2
• Тъй като 2 < 5 се разменят местата им. Текущ масив: 1 4 2 5 8
• Вземат се следващите два елемента от масива: 5 и 8
• Тъй като 5 < 8 не се извършва размяна. Тук спира първото обхождане на масива.

Масивът след първото обхождане има вида: 1 4 2 5 8. Аналогично се извършват по-нататъшни обхождания, докато се стигне до сортирания масив 1 2 4 5 8.

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

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