Como classificar a matriz quase classificada no tempo mais rápido possível? (Java)

Question

Eu tenho uma variedade de valores que é quase, mas não bem classificada, com alguns valores deslocados (digamos, 50 em 100000). Como classificá -lo com mais eficiência? (O desempenho é absolutamente crucial aqui e deve ser muito mais rápido que o O (n)).

Eu sei sobre SmoothSort, mas não consigo encontrar a implementação do Java. Alguém sabe se já foi implementado? Ou o que posso usar para esta tarefa em vez de smoothsort?

Answer 1

Na verdade, a Wikipedia contém uma implementação Java do SmoothSort. Você pode encontrá-lo aqui:

http://en.wikipedia.org/wiki/smoothsort.

Answer 2

Tipo de coquetel

Se você deseja um algoritmo simples que seja fácil de implementar, você pode fazer um tipo de coquetel. Funcionaria razoavelmente bem com entrada quase classificada.

Answer 3

Como o Botz3000 observou, você não pode executar uma operação tão mais rápido que o (n). O elemento mais básico de qualquer algoritmo seria encontrar essas entradas na matriz que estão fora de ordem. Isso requer o (n), mesmo antes de descobrir o que fazer com eles.

Se, de fato, o número de elementos "fora de ordem" são ordens de magnitude abaixo do número total de elementos, você pode usar o seguinte algoritmo (assumindo a lista vinculada):

1. Encontre todos os itens fora de ordem e extraia a lista original para uma lista separada, O (n)
2. O resultado são duas listas: uma lista classificada e uma lista curta extraída
3. Para cada um dos elementos extraídos, insira -os na lista classificada. Isso seria O (log (n)) para cada um, o total é O (xlog (n)), onde x é o número de elementos extraídos. Se x for muito pequeno em relação a n, você acaba com um total de O (n).

Answer 4

Existem muitos bons algoritmos para isso.

Smoothsort é o meu favorito pessoal ... Na verdade, trabalhei em toda a matemática aqui Se você está curioso, por que funciona tão bem.

Um algoritmo bastante bom para dados já classificados é Mergesort natural, que é uma versão de baixo para cima do Mergesort que funciona tratando a entrada como uma sequência de subranges classificados, fazendo vários passes sobre o intervalo que mescla intervalos classificados adjacentes. Ele é executado no tempo O (n) se os dados já forem classificados (porque pode detectar que há apenas um intervalo classificado) e O (n lg n) no pior caso. Esse algoritmo funciona muito bem se os dados forem "classificados em bloco"; Ou seja, consiste em muitos blocos classificados colocados um ao lado do outro.

Definitivamente, a classificação de inserção direta funciona bem para dados principalmente classificados, mas pode degenerar muito mal em muitas entradas. Alguns tipos realmente bons (como introstor) Na verdade, use esta propriedade do tipo de inserção para fazer uma "etapa de limpeza" na entrada.

Answer 5

Sun] JDK7 tem (ou terá) uma implementação de Tim Sort (de Python). É um tipo de mesclagem que aproveita a ordem já existente na matriz.

Answer 6

SmoothSort ou Timsort são ótimos algoritmos e seriam coisas sensatas para usar.

Eu acrescentaria que o que você pode não perceber é que o humilde classificação de inserção é adaptável. De fato, para as listas realmente quase classificadas, como você parece ter, meu entendimento (que não posso apoiar com uma referência) é que ela é mais rápida do que os algoritmos mais sofisticados. O problema é que, se a entrada não for quase derrotada, ela se degrada rapidamente para O (n^2). Ainda assim, é muito simples de implementar corretamente; portanto, se você tiver certeza de que sua entrada é sempre quase derrotada, seria uma boa escolha.

Answer 7

Só para colocá-lo em cima da mesa, um chiclete bem implementado certamente seria o algoritmo mais simples aqui. Com um pior caso de O (n*m), sendo M o número de deslocamentos. A parte M depende fortemente do padrão de deslocamentos, geralmente a complexidade total seria O (n).

Answer 8

Você está certo sobre a impossibilidade de atingir o (n), mas assumindo uma máquina com vários núcleos (que eu tenho), podemos trapacear um pouco usando um algoritmo de classificação paralelo.

Answer 9

Implementar o que chamamos na escola um Classificação da concha. Isso é sub-maiores de bolhas. Uma sub-matriz com a etapa k é uma variedade de elementos com indicios 0, k, 2k, 3k ...

Se você escolher k = 3i+1 e executar vários tipos de bolhas, a partir de mais alto está abaixo de 0, os tempos serão menores em matriz quase classificada.

Answer 10

Esta é a implementação Java original do SmoothSort que costumava estar disponível através do Artigo da Wikipedia.

// by keeping these constants, we can avoid the tiresome business
// of keeping track of Dijkstra's b and c. Instead of keeping
// b and c, I will keep an index into this 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; // the offset of the first element of the prefix into m

  // These variables need a little explaining. If our string of heaps
  // is of length 38, then the heaps will be of size 25+9+3+1, which are
  // Leonardo numbers 6, 4, 2, 1. 
  // Turning this into a binary number, we get b01010110 = 0x56. We represent
  // this number as a pair of numbers by right-shifting all the zeros and 
  // storing the mantissa and exponent as "p" and "pshift".
  // This is handy, because the exponent is the index into L[] giving the
  // size of the rightmost heap, and because we can instantly find out if
  // the rightmost two heaps are consecutive Leonardo numbers by checking
  // (p&3)==3

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      // Add 1 by merging the first two blocks into a larger one.
      // The next Leonardo number is one bigger.
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use 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) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      // This block gets broken into three bits. The rightmost
      // bit is a block of length 1. The left hand part is split into
      // two, a block of length LP[pshift+1] and one of LP[pshift].
      // Both these two are appropriately heapified, but the root
      // nodes are not necessarily in order. We therefore semitrinkle
      // both of them

      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) {
  // we do not use Floyd's improvements to the heapsort sift, because we
  // are not doing what heapsort does - always moving nodes from near
  // the bottom of the tree to the root.

  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; // current node is greater than head. Sift.

    // no need to check this if we know the current node is trusty,
    // because we just checked the head (which is val, in the first
    // iteration)
    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);
  }
}