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

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

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

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

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ě

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

  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