Shell sort

Další významy jsou uvedeny v článku Shell.

Shell sort nebo též Shellovo řazení (ř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).

Časová složitost shell sortu je přibližně rovna n^3/2.

Shell sort v jazyce C/C++

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ě

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

  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

• http://dudka.cz/studyIAL