Smoothsort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Smoothsort

Captura de tela
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso O(n\log n)
complexidade melhor caso O(n)
complexidade de espaços pior caso O(n) total, O(1) auxiliar
otimo Quando os dados já estão ordenados
Algoritmos

algoritmo de ordenação relativamente simples. É um algoritmo de ordenação por comparação

Smoothsort[1] [2] (método) é um algoritmo de ordenação de ordenação por comparação. É uma variação do heapsort desenvolvido por Edsger Dijkstra em 1981. Como o heapsort, o limite superior do smoothsort é de O(n log n). A vantagem de smoothsort é que ele se aproxima de tempo O(n) se a entrada já tem algum grau de ordenação, enquanto a média do heapsort é de O(n log n), independentemente do estado inicial em termos de ordenação.

Panorama[editar | editar código-fonte]

O array a ser ordenado é dividido em uma string de heaps, cada heap com um tamanho igual a um dos números de Leonardo L(n). O processo de divisão é simples - os nós mais à esquerda do array são feitos no maior heap possível, e o restante é dividido igualmente. Pode ser provado que

  • Qualquer array de qualquer tamanho podem assim ser dividido em seções de tamanho L(X).
    Prova: trivial - o menor L(0) é 1.
  • Dois heaps não terão o mesmo tamanho. A string será, portanto, uma cadeia de heaps estritamente decrescente de tamanho. Além disso, uma array de bits pode ser usado para acompanhar quais os números de Leonardo estão sendo usados como tamanhos de heap (a maioria das implementações usa bit-fiddling para fazer isso).
    Prova: Os números de Leonardo L(n) crescem mais lentamente que 2n, e assim para qualquer array sempre haverá um L(n) maior do que a metade do tamanho do array. A exceção é o array de tamanho 2, mas pode ser dividido em duas pilhas de tamanho L(1) e L(0), que são ambas 1 por definição.
  • Dois heaps não terão tamanhos que são números consecutivos de Leonardo, exceto possivelmente os dois finais.
    Prova: Se existe alguma coisa à esquerda - até mesmo um único elemento - após o uso de dois números consecutivos de Leonardo L(x +1) e L(x), poderíamos ter combinado os dois para fazer um pedaço maior de tamanho L(x+2). Como não podemos, não pode haver nada após dois heaps de tamanho L(x+1) e L(x).

Cada heap, tendo um tamanho de L(x), é estruturado a partir da esquerda para a direita como um sub-heap de tamanho L(x-1), uma sub-heap de tamanho L(x-2), e um nó raiz, com excepção dos heaps com um tamanho de L(1) e L(0) (que por definição são 1). Cada heap mantém a propriedade de heap onde um nó raiz é sempre >= os nodos raízes de seus heap-filhos (e, portanto, >= todos os nós em seus heaps filhos), e a string de heaps como um todo mantém a propriedade da string que o nó raiz de cada heap é >= nó raiz do heap para a esquerda.

A conseqüência disto é que o nó mais à direita na string será sempre >= todos os outros nós, e mais importante - um array que já está ordenado não precisa de nenhuma reorganização a ser feita em uma série válida de heaps. Esta é a origem das qualidades de adaptação do algoritmo.

O algoritmo é simples. Começamos por dividir nosso arry não-ordenado em um único heap de um elemento, seguido por uma porção não ordenada. O array de um elemento é trivialmente uma seqüência válida de heaps. Esta seqüência é, então, acrescida pela adição de um elemento de cada vez para a direita, realizando trocas para manter a propriedade da seqüência e a propriedade do heap, até preencher todo o array original.

Deste ponto em diante, o elemento mais à direita da sequência de heaps será o maior elemento em qualquer um dos heaps, e será, portanto, em sua posição final correta. Em seguida, reduzimos a série de heaps de volta a um único heap de um elemento, removendo o nó mais à direita (que permanece no local) e realizamos re-arranjos para restabelecer a condição de heap. Quando reduzimos para um único heap de um elemento, o array é ordenado.

Operações[editar | editar código-fonte]

Ignorando (no momento) as otimizações de Dijkstra, duas operações são necessárias - aumentar a string, adicionando um elemento para a direita, e diminuir a string removendo o elemento mais à direita (a raiz do heap passado), preservando o heap e as condições da string .

Aumentar a string, adicionando um elemento para a direita[editar | editar código-fonte]

  • Se os últimos dois heaps são de tamanho L(x+1) e L(x) (ie: números consecutivos de leonardo), o novo elemento torna-se o nó raiz de um heap maior de tamanho L(x+2). Este heap não necessariamente têm a propriedade heap.
  • Se os últimos dois heaps das strings não são números consecutivos de Leonardo, então o elemento mais à direita torna-se um novo heap de tamanho 1. Este 1 é levado a L(1), a menos que o heap da direita já tenha o tamanho L(1), caso em que o novo heap de um elemento é considerado como sendo de tamanho L(0).

Após isto, o heap e as propriedades da string devem ser restaurados. Para fazer isso,

  1. O Heap mais a direita (o que acaba de ser criado) torna-se o "heap" corrente.
  2. Enquanto existe um heap à esquerda do heap atual e sua raiz é maior do que a raiz atual e também das raízes dos heaps filhos.
  3. * Então troque a nova raiz com a raiz no heap à esquerda (o que não vai perturbar a propriedade heap da pilha actual). Este heap se torna então o heap atual.
  4. Execute uma operação de "filtro" no heap atual para estabelecer a propriedade de heap:
  5. *, Enquanto o heap atual tem um tamanho maior que 1 e tanto o heap-filho do heap corrente tem um nó raiz maior do que a raiz do heap corrente
  6. ** Troque a maior raiz filha com a raiz atual. Esse heap filho torna-se o heap corrente

A operação do filtro é bastante simplificada pelo uso de números de Leonardo, pois um heap será sempre um único nó, ou terá dois heaps-filho. Não é preciso se tratar a condição de um dos heaps-filho não estar presente.

Optimização[editar | editar código-fonte]

  • Se o novo heap vai se tornar parte de uma grande heap no momento em que terminamos, então não se deve preocupar em estabelecer a propriedade de string: ela só precisa ser feita quando um heap atingiu seu tamanho final.
    • Para fazer isso, olhe quantos elementos são deixados após o novo heap de tamanho L(x). Se houver mais do que L(x-1)+1, então este novo heap está a caminho de ser intercalado.
  • Não mantenha a propriedade heap do heap mais à direita. Se este heap se torna um dos heaps finais da string então manter a propriedade string irá restaurar a propriedade heap. Claro, sempre que um novo heap é criado, em seguida, o heap que era o mais à direita já não é o mais à direita e à propriedade heap precisa ser restaurada.

Encolher a seqüência pela remoção do elemento mais à direita[editar | editar código-fonte]

Se o heap mais à direita tem um tamanho de 1 (ou seja, L(1) ou L(0)), então nada precisa ser feito. Basta remover o heap mais à direita.

Se o heap mais à direita não tem um tamanho de 1, em seguida, remover a raiz, mostrando os dois sub-heaps, como membros da string. Restaurar a propriedade de string primeiro na esquerda e, em seguida, na direita.

Otimização[editar | editar código-fonte]

  • Ao restaurar a propriedade string, não precisamos comparar a raiz do heap para a esquerda com os dois nós filhos dos heaps que acabam de ser expostos, pois sabemos que estes heaps recentemente expostos têm a propriedade de heap. Basta compará-lo com a raiz.

Implementação em Java[editar | editar código-fonte]

Este código usa lo e hi como as os limites do array inclusive. Note-se que esta não é a convenção usual.

  // mantendo essas constantes, podemos evitar o negócio cansativo
  // de acompanhar o b e o c de Dijkstra. Em vez de manter
  // b e c, Eu irei manter um índice dentro do array
 
  static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
      177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
      35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
      1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
      48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
      866988873 // the next number is > 31 bits.
  };
 
  public static <C extends Comparable<? super C>> void sort(C[] m,
      int lo, int hi) {
    int head = lo; // o deslocamento do primeiro elemento do prefixo em m
 
    // Essas variáveis precisam de um pouco de explicação. Se a nossa string de heaps
    // é de tamanho 38, então os heaps serão de tamanho 25+9+3+1, que são os
    // números de Leonardo 6, 4, 2, 1. 
    // Passando este int um número binário, temos b01010110 = x56. Nós representamos
    // este número como um par de números, através de deslocamentos à direita de todos os zeros  
    // armazenando a mantissa e o expoente como "p" e "pshift".
    // Isso é útil, porque o expoente é o índice em L [] dando o
    // tamanho fo heap mais a direita, e porque nós podemos imediatamente verificar se
    // os dois heaps mais a direita são números consecutivos de leonardo, verificando
    // (p&3)==3
 
    int p = 1; // o bitmap da concatenação padrão atual >> pshift
    int pshift = 1;
 
    while (head < hi) {
      if ((p & 3) == 3) {
        // Soma 1 intercalando os dois primeiros blocos em um bloco maior.
        // O próximo número de Leonardo é maior em um.
        sift(m, pshift, head);
        p >>>= 2;
        pshift += 2;
      } else {
        // somando um novo bloco de tamanho 1
        if (LP[pshift - 1] >= hi - head) {
          // this block is its final size.
          trinkle(m, p, pshift, head, false);
        } else {
          // este bloco esrá intercalado.
          sift(m, pshift, head);
        }
 
        if (pshift == 1) {
          // LP[1] está sendo usado, logo nós adicionamos o uso de LP[0]
          p <<= 1;
          pshift--;
        } else {
          // shift out to position 1, add LP[1]
          p <<= (pshift - 1);
          pshift = 1;
        }
      }
      p |= 1;
      head++;
    }
 
    trinkle(m, p, pshift, head, false);
 
    while (pshift != 1 || p != 1) {
      if (pshift <= 1) {
        // bloco de comprimento 1. Nenhum fiddling necessário
        int trail = Integer.numberOfTrailingZeros(p & ~1);
        p >>>= trail;
        pshift += trail;
      } else {
        p <<= 2;
        p ^= 7;
        pshift -= 2;
 
        // ok. Este bloco é quebrado em três pedaços. O bit mais à direita
        // é um bloco de tamanho. A parte da esquerda é dividida em dois,
        // um bloco de tamanho LP[pshift+1] e um de LP[pshift].
        // Ambos os dois são adequadamente heaps formados, mas os nodos raiz
        // não estão necessariamente ordenados. 
        // Por isso, chamamos trinkle para ambos
 
        trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
        trinkle(m, p, pshift, head - 1, true);
      }
 
      head--;
    }
  }
 
  private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
      int head) {
 
    C val = m[head];
 
    while (pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
 
      if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
        break;
      if (m[lf].compareTo(m[rt]) >= 0) {
        m[head] = m[lf];
        head = lf;
        pshift -= 1;
      } else {
        m[head] = m[rt];
        head = rt;
        pshift -= 2;
      }
    }
 
    m[head] = val;
  }
 
  private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
      int pshift, int head, boolean isTrusty) {
 
    C val = m[head];
 
    while (p != 1) {
      int stepson = head - LP[pshift];
 
      if (m[stepson].compareTo(val) <= 0)
        break; // o nodo corrente é maior que a cabeça. peneirar.
 
      // não há necessidade de checar isso, se sabemos que o nodo atual é confiável, 
      // porque nós já checamos a cabeça (que é val, na primeira iteração)
      if (!isTrusty && pshift > 1) {
        int rt = head - 1;
        int lf = head - 1 - LP[pshift - 2];
        if (m[rt].compareTo(m[stepson]) >= 0
            || m[lf].compareTo(m[stepson]) >= 0)
          break;
      }
 
      m[head] = m[stepson];
 
      head = stepson;
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
      isTrusty = false;
    }
 
    if (!isTrusty) {
      m[head] = val;
      sift(m, pshift, head);
    }
  }

Referências

Ligações externas[editar | editar código-fonte]