Shell sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Další významy jsou uvedeny v článku Shell.

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í nebude).

Asymptotická složitost je O(n^2). Přesto je shell sort z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost shell sortu je přibližně rovna n^{3/2}.

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 setřídí 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]