Shellovo řazení

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Shell sort)
Skočit na: Navigace, Hledání
Další významy jsou uvedeny na stránce Shell.
Shell sort algoritmus barevné pruhy

Shellovo řazení (anglicky shell sort, nebo též řazení se snižujícím se přírůstkem) je řadicí algoritmus podobný insert sortu, který objevil a v roce 1959 publikoval Donald Shell.

Shell sort 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 shell sort z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost shell sortu je přibližně rovna .

Princip[editovat | editovat zdroj]

Shell sort funguje podobně jako insert sort. Ovšem shell sort 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í insert sortu. 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 vkládáním (sekvence od Marcin Ciura):

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
{
    # Do an insertion sort for each gap size.
    for (i = gap; i < n; i += 1)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }

}

Shell sort v jazyce C/C++[editovat | editovat zdroj]

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

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

Shell sort v Javě[editovat | editovat zdroj]

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

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

Shell sort v Pythonu[editovat | editovat zdroj]

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

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

Reference[editovat | editovat zdroj]