Gyorsrendezés

A rendezés hasonlít az ókori oszd meg és uralkodj mondáshoz. A rendezés elve rekurzív. Két részre osztjuk a rendezendő sorozatot úgy, hogy az egyik rész minden eleme kisebb a másik rész összes eleménél. A két részre pedig külön-külön ismételjük meg az előbbi lépést, míg mindkét rész 0 vagy 1 elemű lesz.

A feldolgozási művelet egy szétválogatás, melynek során egy megadott értékhez viszonyítva a tőle kisebb elemeket elé, a nagyobbakat mögé helyezzük. Viszonyítási értéknek a gyakorlatban a sorozat középső vagy első elemét célszerű kiválasztani.

Az algoritmus előnye, hogy a legtöbb architektúrán nagyon hatékonyan implementálható, és az adatok jellegének ismeretében az algoritmus egyes elemei megválaszthatók úgy, hogy csak nagyon ritkán fusson négyzetes ideig. A futási idő átlagos esetben n * log n

Egy lehetséges implementáció:

using System;

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

        public static void Gyorsrendez(int[] tomb, int eleje, int vege)
        {
            if (eleje < vege)
            {
                int kozepe = Feloszt(tomb, eleje, vege);
                Gyorsrendez(tomb, eleje, kozepe - 1);
                Gyorsrendez(tomb, kozepe + 1, vege);
            }
        }

        private static int Feloszt(int[] tomb, int eleje, int vege)
        {
            int kozepe = tomb[vege];
            int kozepindex = eleje;

            for (int i = eleje; i < vege; i++)
            {
                if (tomb[i] <= kozepe)
                {
                    int temp = tomb[i];
                    tomb[i] = tomb[kozepindex];
                    tomb[kozepindex] = temp;
                    kozepindex++;
                }
            }

            int kozepindexErteke = tomb[kozepindex];
            tomb[kozepindex] = tomb[vege];
            tomb[vege] = kozepindexErteke;
            return kozepindex;
        }

        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("Gyors rendezés:");
            Gyorsrendez(tomb, 0, tomb.Length - 1);
            TombKiir(tomb);

            Console.ReadKey();
        }
    }
}

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: