Buborékos rendezés

Az algoritmus a nevét onnan kapta, hogy hasonlóan ahhoz, ahogy a pezsgőspohárban szállnak felfelé a buborékok, a rendezés során is minden egyes menetben a fennmaradó elemek közül a legnagyobbat “áramoltatjuk fel” a tömbszelet végére, tetejére.

A rendezés során a tömb fennmaradó részén végighaladva az egymás utáni szomszédos elemeket összehasonlítjuk, és ha szükséges, megcseréljük őket, hogy közülük mindig a nagyobb helyezkedjen el feljebb.

Ezt a műveletet aztán a tömbön feljebb lépve addig ismételjük, amíg a fennmaradó rész végéhez nem érünk. A műveletsor végén a rendezetlen rész tetejére mindig a legnagyobb érték kerül majd fel, amelyet a következő menetben már nem veszünk figyelembe. A ciklust egészen addig ismételjük a fennmaradó halmazon, amíg már csak egyetlen elem marad.

Egy lehetséges implementáció:

public static int[] BuborekRendez(int[] bemenet)
{
    int[] tomb = new int[bemenet.Length];
    Array.Copy(bemenet, tomb, bemenet.Length);
    for (int i = tomb.Length -1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (tomb[j] > tomb[j + 1])
            {
                int tmp = tomb[j];
                tomb[j] = tomb[j + 1];
                tomb[j + 1] = tmp;
            }
        }
    }
    return tomb;
}

Az algoritmus futási ideje javítható, ha megfigyeljük, hogy a külső ciklusnak csak akkor érdemes tovább futnia, ha a belső ciklusban volt csere. Erre bevezethetünk egy logikai változót, így a javított algoritmus a következőképpen néz ki:

using System;

namespace PeldaAlgoritmusokBuborekrendez
{
    class Program
    {
        static void TombKiir(int[] tomb)
        {
            foreach (var elem in tomb)
            {
                Console.Write("{0}, ", elem);
            }
            Console.WriteLine();
        }

        public static int[] BuborekRendez(int[] bemenet)
        {
            int[] tomb = new int[bemenet.Length];
            Array.Copy(bemenet, tomb, bemenet.Length);
            var csere = true;
            for (int i = tomb.Length - 1; i >= 0 && csere; i--)
            {
                csere = false;
                for (int j = 0; j < i; j++)
                {
                    if (tomb[j] > tomb[j + 1])
                    {
                        int tmp = tomb[j];
                        tomb[j] = tomb[j + 1];
                        tomb[j + 1] = tmp;
                        csere = true;
                    }
                }
            }
            return tomb;
        }

        static void Main(string[] args)
        {
            var tomb = new int[] { 9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6 };

            Console.WriteLine("Rendezés előtt:");
            TombKiir(tomb);

            Console.WriteLine("Buborék rendezés:");
            var bubi = BuborekRendez(tomb);
            TombKiir(bubi);

            Console.ReadKey();
        }
    }
}

A javított algoritmus futási ideje legjobb esetben lineáris lesz, legrosszabb esetben pedig négyzetes.

A program kimenete:

Rendezés elott:
9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6, 
Minimum rendezés:
0, 0, 1, 1, 2, 2, 2, 2, 3, 4, 5, 6, 6, 8, 8, 9, 

Az algoritmus egy vizuális reprezentációja a YouTube-on: https://www.youtube.com/watch?v=Cq7SMsQBEUw