Shell rendezés

Nevét a feltalálójáról, Donald Shell-ről kapta, aki a módszert 1959-ban találta ki. Ez nem egy új módszer, hanem több, már megismert módszerhez illeszthető optimalizáció. Az alapelv az, hogy sokat javíthat a rendezésen, ha először az egymástól nagy távolságra lévő elemeket hasonlítjuk, cseréljük, mert így az egyes elemek gyorsabban közel kerülhetnek a végleges helyükhöz.

A módszer leginkább a beszúró rendezés hatékonyságának növelését szokta szolgálni, a legrosszabb esetben mérhető futási időt csökkenti négyzetesről. A tényleges hatékonyságot pszeudókód esetén nem lehet mérni.

A konkrét sebesség befolyásoló tényező az, hogy mi alapján döntjük el, hogy két elem egymástól távol áll, vagy sem. Erre egy ugrássorozatot szoktak definiálni. Minden ugrássorozat működőképes, amennyiben az tartalmazza az egyes értéket. A legjobb eredményeket az a számsorozat adja, amiben a következő elem az előző elem 2.2-vel[^1] szorzott és kerekített, a legközelebbi egészre.

Egy lehetséges implementáció:

using System;

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

        public static int[] ShellSort(int[] bemenet)
        {
            int[] tomb = new int[bemenet.Length];
            Array.Copy(bemenet, tomb, bemenet.Length);
            int tavolsag = tomb.Length / 2;
            while (tavolsag > 0)
            {
                //ez egy módosított beszúró rendezés
                for (int i = 0; i < tomb.Length - tavolsag; i++)
                {
                    int j = i + tavolsag;
                    int tmp = tomb[j];
                    while (j >= tavolsag && tmp < tomb[j - tavolsag])
                    {
                        tomb[j] = tomb[j - tavolsag];
                        j -= tavolsag;
                    }
                    tomb[j] = tmp;
                }
                if (tavolsag == 2) tavolsag = 1;
                else tavolsag = (int)(tavolsag / 2.2);
            }
            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("Shell rendezés:");
            var shell = ShellSort(tomb);
            TombKiir(shell);

            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:

[1]: Gastón H Gonnet & Ricardo Baeza-Yates Handbook of algorithms and data structures: in Pascal and C (2nd ed.) könyvében ajánlott érték. ISBN: 978-0-201-41607-7