Beszúró rendezés

A beszúró rendezés nevét onnan kapta, hogy a működése leginkább a kártyalapok egyenként való kézbe vételéhez és a helyükre igazításához hasonlítható.

Vesszük a soron következő elemet, és megkeressük a helyét a tőle balra lévő, már rendezett részben, majd a kereséssel párhuzamosan a nagyobb elemeket rendre eggyel jobbra mozgatjuk. Az aktuális elemet egy segédváltozóban tároljuk, mert a mozgatások során értéke felülíródhat egy nagyobb elemmel.

Ezen algoritmus használata akkor igazán előnyös, ha az adatsorunk már részben rendezett. Továbbá akkor igen hatékony, ha egy rendezett sorozatot bővítünk és a bővítés után is szeretnénk, hogy a sorozat rendezett maradjon.

Az algoritmus futási ideje legjobb esetben konstans, vagyis a gép sebességétől függ, az elemektől nem. Legrosszabb esetben pedig négyzetes.

Egy példa implementáció:

using System;

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

        public static int[] Beszurorendez(int[] bemenet)
        {
            int[] tomb = new int[bemenet.Length];
            Array.Copy(bemenet, tomb, bemenet.Length);
            for (var i = 0; i < tomb.Length - 1; i++)
            {
                var j = i + 1;
                while (j > 0)
                {
                    if (tomb[j - 1] > tomb[j])
                    {
                        var temp = tomb[j - 1];
                        tomb[j - 1] = tomb[j];
                        tomb[j] = temp;
                    }
                    j--;
                }
            }
            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("Beszúró rendezés:");
            var beszur = Beszurorendez(tomb);
            TombKiir(beszur);

            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: https://www.youtube.com/watch?v=8oJS1BMKE64