Wie Art zu fast Array in der schnellsten Zeit möglich sortiert? (Java)

Question

Ich habe ein Array von Werten, die fast, aber nicht ganz sortiert, wobei einige Werte verschoben (beispielsweise 50 in 100000). Wie sortieren es am effizientesten? (Leistung ist hier absolut entscheidend und sollte viel schneller als O (N) sein).

weiß ich über Smoothsort, aber ich kann nicht Java-Implementierung finden. Weiß jemand, ob es bereits umgesetzt wird? Oder, was ich für diese Aufgabe verwenden statt Smoothsort?

Answer 1

Tatsächlich enthält die Wikipedia eine Java-Implementierung von Smoothsort. Sie können es hier finden:

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

Answer 2

Shakersort

Wenn Sie einen einfachen Algorithmus wollen, die einfach zu implementieren ist, könnten Sie eine Shakersort tun. Es würde auf fast sortierten Eingang recht gut arbeiten.

Answer 3

Wie Botz3000 erwähnt, können Sie nicht ausführen eine solche Operation schneller als O (N). Das grundlegendste Element eines Algorithmus wäre die Einträge in dem Array zu finden, die von Ordnung aus. Dies erfordert O (N), noch bevor Sie herausfinden, was mit ihnen zu tun.

Wenn in der Tat die Zahl der „out-of-order“ Elemente Größenordnungen unter der Gesamtzahl der Elemente ist, können Sie den folgenden Algorithmus verwenden (verknüpfte Liste vorausgesetzt):

1. Alle Out-of-Order-Artikel und Dekomprimierung der von der ursprünglichen Liste in eine separate Liste, O (N)
2. Das Ergebnis sind zwei Listen: eine sortierte Liste und eine kurze Liste extrahierter
3. Für jedes der extrahierten Elemente, um sie in der sortierten Liste einzufügen. Das wäre O (log (N)) für jeweils insgesamt O (Xlog (N)), wobei X die Anzahl der extrahierten Elemente ist. Wenn X N sehr klein ist, am Ende mit insgesamt O (N) nach oben.

Answer 4

Es gibt viele gute Algorithmen für diese.

Smoothsort ist mein persönlicher Favorit ... Ich arbeitete tatsächlich alle Mathe aus hier Wenn Sie neugierig, warum es funktioniert so gut.

Ein ziemlich guter Algorithmus für die bereits sortierten Daten ist natürlicher mergesort , die eine von unten nach oben ist die Version von Mergesort, dass die Arbeiten von der Eingabe als eine Folge von sortierten Teilbereichen zu behandeln, dann mehrere Herstellung übergeht der Bereich angrenzend sortierten Bereiche zu verschmelzen. Es läuft in O (n) Zeit, wenn die Daten bereits sortiert sind (weil es erkennen kann, dass es nur ein sortierten Bereich) und O (n lg n) im schlechtesten Fall. Dieser Algorithmus funktioniert recht gut, wenn die Daten „Block sortiert“; Das heißt, es von vielen sortierten Blöcken besteht direkt aneinander angeordnet.

Gerade Insertionsort funktioniert auf jeden Fall gut für meist sortierten Daten, sondern degenerieren kann sehr schlecht auf eine Menge von Eingaben. Einige wirklich gute Sorten (wie Introsort ) tatsächlich diese Eigenschaft des Einsetzens verwendet Art einen „Bereinigungsschritt“ am Eingang zu tun.

Answer 5

[Sun] JDK7 hat (oder haben) eine Implementierung von Tim sortieren (aus Python). Es ist eine Mergesort die die Vorteile der Reihenfolge in der Anordnung vorhandenen nimmt bereits.

Answer 6

Smoothsort oder Timsort sind große Algorithmen und vernünftige Dinge zu verwenden wäre.

Ich würde hinzufügen, dass das, was Sie vielleicht nicht wissen ist, dass die bescheidene Insertionsort ist adaptiv. Denn für wirklich fast sortierte Listen, wie Sie zu haben scheinen, mein Verständnis (was ich nicht mit einem Referenz sichern kann) ist, dass es schneller als die anspruchsvolleren Algorithmen. Das Problem ist, dass, wenn der Eingang nicht fast sortiert, es schnell abbaut bis O (n ^ 2). Dennoch ist es sehr einfach korrekt zu implementieren, so dass, wenn Sie sicher sind, dass Sie Ihre Eingabe immer fast sortiert ist, wäre es eine gute Wahl sein.

Answer 7

Just es auf den Tisch zu legen, eine gut umgesetzt blasen Art wäre sicherlich der einfachste Algorithmus sein hier. Mit einer Worst-Case von O (n * m), wobei m die Anzahl der Verschiebungen. Der m Teil hängt stark von dem Muster der Verschiebungen, in der Regel Gesamtkomplexität wäre O (n).

Answer 8

Sie haben Recht, über die Unmöglichkeit, O (N), sondern eine Multi-Core-Maschine unter der Annahme (die ich habe), können wir ein wenig betrug durch einen parallelen Sortieralgorithmus verwendet wird.

Answer 9

umzusetzen, was wir in der Schule einer Shell sortieren genannt. Das ist, bubblesorting Unteranordnungen. Eine Unteranordnung mit dem Schritt k ist eine Anordnung von Elementen mit indicies 0, k, 2k, 3k ...

Wenn Sie k = 3i + 1, und führen Sie mehrere Blasen Sorten, ausgehend von höheren i-s downto 0, die mal kleiner auf fast-sortierten Array sein wird.

Answer 10

Dies ist die ursprüngliche Java-Implementierung von Smoothsort, die über die Wikipedia-Artikel .

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