Shellovo řazení

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 $O(n^{2})$ . Přesto je Shellovo řazení z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost Shellova řazení je přibližně rovna $n^{3/2}$ .

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 range(prirustek, len(a)):
              for j in range(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]