Shellovo řazení

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Další významy jsou uvedeny na stránce Shell.
Shellovo řazení algoritmus barevné pruhy

Shellovo řazení, známé také pod anglickým jménem Shell sort nebo též řazení se snižujícím se přírůstkem, je řadicí algoritmus podobný algoritmu řazení vkládáním, který objevil a v roce 1959 publikoval Donald Shell.

Shellovo řazení je nestabilní řadicí metoda (tj. nezachovává původní pořadí dvou prvků se stejným klíčem - mají-li prvky X a Y stejný klíč a v původním neseřazeném poli se prvek X vyskytuje před prvkem Y, ve výsledném seřazeném poli tomu tak po použití nestabilního řazení nemusí být).

Asymptotická složitost je . Přesto je Shellovo řazení z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost Shellova řazení je přibližně rovna .

Princip[editovat | editovat zdroj]

Shellovo řazení funguje podobně jako řazení vkládáním. Ovšem Shellovo řazení neřadí prvky umístěné vedle sebe, nýbrž prvky mezi nimiž je určitá mezera. V každém následujícím kroku je mezera zmenšena. V okamžiku, kdy je mezera zmenšena na velikost 1, tak je principiálně řazeno pomocí řazení vkládáním. Výhoda tohoto přístupu (řazení se snižujícím se přírůstkem) je rychlé přemístění nízkých a vysokých hodnot. Poslední iterace totiž přesune jen minimum prvků.

Velikost mezery[editovat | editovat zdroj]

Aby byla zajištěna nejvyšší efektivita algoritmu, je potřeba zvolit ideální velikost mezery. Marcin Ciura zjistil, že ideální mezerou je 2,2. Jako počáteční mezera je tedy v algoritmu použita největší možná z řady čísel: 1, 4, 10, 23, 57, 132, 301, 701, ... (celočíselné násobky 2,2).

Implementace[editovat | editovat zdroj]

Pseudokód s vnitřním řazením vkládáním (posloupnost od Marcin Ciura):

# řazení v poli a[0...n-1].
mezery = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (mezera in mezery)
{
    # Proveďte řazení vkládáním pro každou velikost mezery.  
    for (i = mezera; i < n; i += 1)
    {
        temp = a[i]
        for (j = i; j >= mezera and a[j - mezera] > temp; j -= mezera)
        {
            a[j] = a[j - mezera]
        }
        a[j] = temp
    }

}

Shellovo řazení v jazyce C/C++[editovat | editovat zdroj]

Následující implementace Shellova řazení v jazyce C seřadí pole celočíselných typů (intů).

void shellovo_razeni(int A[], int velikost) {
  int i, j, prirustek, temp;
  prirustek = velikost / 2;
      
  while (prirustek > 0) {
    for (i = prirustek; i < velikost; i++) {
      j = i;
      temp = A[i];
      while ((j >= prirustek) && (A[j-prirustek] > temp)) {
        A[j] = A[j - prirustek];
        j = j - prirustek;
      }
      A[j] = temp;
    }
    
    if (prirustek == 2)
       prirustek = 1;
    else 
       prirustek = (int) (prirustek / 2.2);
  }
}

Shellovo řazení v Javě[editovat | editovat zdroj]

Implementace v Javě je následující:

public static void shellovoRazeni(int[] a) {
    for (int prirustek = a.length / 2; prirustek > 0;
          prirustek = (prirustek == 2 ? 1 : (int) Math.round(prirustek / 2.2))) {
        for (int i = prirustek; i < a.length; i++) {
            int temp = a[i];
            for (int j = i; j >= prirustek && a[j - prirustek] > temp; j -= prirustek){
                a[j] = a[j - prirustek];
                a[j - prirustek] = temp;
            }
        }
    }
}

Shellovo řazení v Pythonu[editovat | editovat zdroj]

  def shellovorazeni(a):
      def prirustek_generator(a):
          h = len(a)
          while h != 1:
              if h == 2:
                  h = 1
              else: 
                  h = 5*h//11
              yield h

      for prirustek in prirustek_generator(a):
          for i in xrange(prirustek, len(a)):
              for j in xrange(i, prirustek-1, -prirustek):
                  if a[j - prirustek] < a[j]:
                      break
                  a[j], a[j - prirustek] = a[j - prirustek], a[j]
      return a

Reference[editovat | editovat zdroj]