Shell sort

Shell sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	depende da sequência do gap. Melhor conhecida: $O(n\log _{2}n)$[carece de fontes]
complexidade caso médio	depende da sequência do gap
complexidade melhor caso	$O(n\log _{2}n)$[carece de fontes]
complexidade de espaços pior caso	$O(n)$
Algoritmos

Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo. Veja a versão em inglês desse mesmo link.

Shell sort visualizado em barras

Código em Java

public static void shellSort(Integer[] nums) {
    int h = 1;
    int n = nums.length;
    
    while(h < n) {
            h = h * 3 + 1;
    }
    
    h = h / 3;
    int c, j;
    
    while (h > 0) {
        for (int i = h; i < n; i++) {
            c = nums[i];
            j = i;
            while (j >= h && nums[j - h] > c) {
                nums[j] = nums[j - h];
                j = j - h;
            }
            nums[j] = c;
        }
        h = h / 2;
    }
}

Código em Python

def shellSort(nums):
    h = 1
    n = len(nums)
    while h > 0:
            for i in range(h, n):
                c = nums[i]
                j = i
                while j >= h and c < nums[j - h]:
                    nums[j] = nums[j - h]
                    j = j - h
                    nums[j] = c
            h = int(h / 2.2)
    return nums

Código em C++11

template <typename T>
void shell_sort(std::vector<T> &v) {

    int h = 1;
    int i, j;
    int rep = 0;

    while (h < v.size()) {
       h = h*3+1;
    }

    while (h > 1) {
        h /= 3;

        for (i = h; i < v.size(); i++) {
            T aux = v[i];
            j = i;

            while (j >= h && aux < v[j-h]) {
                v[j] = v[j-h];
                j -= h;
                rep++;
            }

            v[j] = aux;
        }
    }
}

Código em C

void shellSort(int *vet, int size) {
    int i, j, value;
 
    int h = 1;
    while(h < size) {
        h = 3*h+1;
    }
    while (h > 0) {
        for(i = h; i < size; i++) {
            value = vet[i];
            j = i;
            while (j > h-1 && value <= vet[j - h]) {
                vet[j] = vet[j - h];
                j = j - h;
            }
            vet[j] = value;
        }
        h = h/3;
    }
}

Código em PHP

function shellSort($arr_sort){
   $pet = 1;
   do {
      $pet = 3 * $pet + 1;
   } while ($pet < count($arr_sort));
   do {
      $pet /= 3;
      $pet = intval($pet);
      for ($i = $pet; $i < count($arr_sort); $i++) {
         $temp = $arr_sort[$i];
         $j = $i - $pet;
         while($j >=0 && $temp < $arr_sort[$j]) {
            $arr_sort[$j + $pet] = $arr_sort[$j];
            $j -= $pet;
         }
         $arr_sort[$j + $pet] = $temp;
      }
   } while ($pet > 1);
   return $arr_sort;
}

Código em Ruby

def shellSort(array)
  n = array.length
  h = n/2

  while h > 0
    for i in (h...n)
      c = array[i]
      j = i

      while j  >= h && c < array[j-h]
        array[j] = array[j-h]
        j = j-h
        array[j] = c
      end
    end

    h = (h/2.2).to_i
  end
end

Código em Swift

func shellSort<T:Comparable>(_ input:[T]) -> [T] {

    var items       : [T] = input
    let itemsCount  : Int = items.count
    var gapSize     : Int = items.count
    let minGapSize  : Int = 1
    let half        : Int = 2
    var swaped      : Bool = true
    
    while !swaped || gapSize > minGapSize {
        
        swaped  = false
        gapSize = (gapSize + 1) / half
        
        for (index, _) in items.enumerated() where index < (itemsCount - gapSize) {
            let indexToCompare = index + gapSize
            if items[index] > items[indexToCompare] {
                swap(&items[index], &items[indexToCompare])
                swaped = true
            }
        }
    }
    
    return items
}

Código em JavaScript

public void shellSort(int[] array) {
     int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 };
     int temp;
     int i, j;

     for (int gap : gaps) {
          for (i = gap; i < array.length; i++) {
               temp = array[ i ];
               for (j = i; j >= gap && array[ j - gap ] > temp; j -= gap) {
                    array[ j ] = array[ j - gap ];
               }
               array[ j ] = temp;
          }
     }
}

Exemplo de execução

Execução:

Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9

1, 43, 12, 6, 56, 23, 52, 9

1, 6, 12, 43, 56, 23, 52, 9

1, 6, 12, 43, 52, 23, 56, 9

1, 6, 12, 9, 52, 23, 56, 43

1, 6, 9, 12, 52, 23, 56, 43

1, 6, 9, 12, 23, 52, 56, 43

1, 6, 9, 12, 23, 52, 43, 56

1, 6, 9, 12, 23, 43, 52, 56

Em negrito estão os números trocados na atual iteração.

Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.

Conclusão

A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na sequência obtida. Devido a sua complexidade possui excelentes desempenhos em N muito grandes, inclusive sendo melhor que o Merge Sort.

Ver também

• Ordenação de vector
• Quick sort
• Bubble sort
• Selection sort
• Pesquisa binária
• sort-merge utility
• Heapsort
• Radix sort