Comment trier presque tableau trié dans le temps le plus rapide possible? (Java)

Question

J'ai un tableau de valeurs qui est presque, mais pas tout à fait triée, avec quelques valeurs déplacées (disons, 50 à 100000). Comment trier le plus efficacement possible? (Performance est absolument cruciale ici et devrait être beaucoup plus rapide que O (N)).

Je sais smoothsort, mais je ne peux pas trouver l'application Java. Est-ce que quelqu'un sait s'il est déjà mis en œuvre? Ou ce que je peux utiliser pour cette tâche au lieu de smoothsort?

Answer 1

En fait, la Wikipédia contient une implémentation Java de smoothsort. Vous pouvez le trouver ici:

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

Answer 2

Trier Cocktail

Si vous voulez un algorithme simple qui est facile à mettre en œuvre, vous pouvez faire un cocktail sorte . Il fonctionnerait assez bien sur l'entrée presque triés.

Answer 3

Comme Botz3000 noté, vous ne pouvez pas effectuer une telle opération plus rapide que O (N). L'élément le plus fondamental de tout algorithme serait de trouver les entrées dans le tableau qui sont hors d'usage. Cela nécessite O (N), même avant de savoir quoi faire avec eux.

En effet, si le nombre de « out-of-order » éléments ordres de grandeur en dessous du nombre total d'éléments, vous pouvez utiliser l'algorithme suivant (en supposant liste chaînée):

1. Trouvez tous les contrôles hors commande articles et extraire la de la liste initiale à une liste séparée, O (N)
2. Le résultat est deux listes: une liste triée et une courte liste extraite
3. Pour chacun des éléments extraits, de les insérer dans la liste triée. Ce serait O (log (N)) pour chacun, total est O (Xlog (N)), où X est le nombre des éléments extraits. Si X est très faible par rapport à N, vous vous retrouvez avec un total de O (N).

Answer 4

Il y a beaucoup de bons algorithmes pour cela.

smoothsort est mon préféré ... En fait, je travaillais tous les maths si vous êtes curieux de savoir pourquoi cela fonctionne si bien.

Un algorithme assez bon pour les données déjà trié est mergesort naturel , qui est une version ascendante de mergesort qui fonctionne en traitant l'entrée comme une séquence de sous-zones triées, puis faire des passes multiples sur la plage de fusion des plages adjacentes triées. Il fonctionne en O (n) si les données sont déjà triées (car il peut détecter qu'il n'y a qu'une seule plage triée) et O (nlogn) dans le pire des cas. Cet algorithme fonctionne très bien si les données sont « bloc triée »; qui est, il se compose d'un grand nombre de blocs triés placé juste à côté de l'autre.

insertion droite genre fonctionne vraiment bien pour les données triées principalement, mais peut dégénérer très mal sur beaucoup d'intrants. Quelques très bonnes sortes (comme introsort ) réellement utiliser cette propriété de sorte d'insertion à faire une « étape de nettoyage » sur l'entrée.

Answer 5

[Sun] JDK7 a (ou aura) une mise en œuvre de Tim sorte (de Python). Il est une sorte de fusion qui profite de l'ordre existant déjà dans le tableau.

Answer 6

smoothsort ou Timsort sont grands algorithmes, et les choses seraient sensibles à utiliser.

Je rajouterais que ce que vous pourriez ne pas réaliser est que les href="http://en.wikipedia.org/wiki/Insertion_sort" humbles sorte est adaptatif. En effet, pour les listes vraiment triées presque, comme vous semblez avoir, je crois comprendre (ce que je ne peux pas sauvegarder avec une référence) est qu'il est plus rapide que les algorithmes plus sophistiqués. Le problème est que si l'entrée est à peu près pas-triés, il se dégrade rapidement en O (n ^ 2). Pourtant, il est très simple à mettre en œuvre correctement, donc si vous êtes sûr que votre entrée est toujours presque triée, ce serait un bon choix.

Answer 7

Juste pour le mettre sur la table, un puits mis en œuvre bulle tri serait certainement l'algorithme le plus simple ici. Avec un pire cas de O (n * m), m étant le nombre de déplacements. La partie m dépend en grande partie sur le modèle des déplacements, le plus souvent la complexité totale serait O (n).

Answer 8

Vous avez raison de l'impossibilité d'atteindre O (N), mais en supposant une machine multi-core (que j'ai), on peut tricher un peu en utilisant un algorithme de tri parallèle.

Answer 9

METTRE EN OEUVRE ce que nous appelions à l'école trier Shell . C'est bubblesorting sous-réseaux. Un sous-réseau à l'étape k est une matrice d'éléments avec indicies 0, k, 2k, 3k ...

Si vous choisissez k = 1 + 3 decies et d'effectuer plusieurs sortes de bulles, à partir de i-s downto 0 plus, les temps seront plus petits sur la matrice presque triées.

Answer 10

Ceci est l'implémentation Java originale de smoothsort qui était autrefois disponible via le Wikipedia article .

// 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);
  }
}