Wie sortiere ich direkt mit dem Sortieralgorithmus?

244

Ich weiß, dass die Frage nicht zu spezifisch ist.

Ich möchte nur, dass mir jemand sagt, wie eine normale Zusammenführungssortierung in eine direkte Zusammenführungssortierung (oder eine Zusammenführungssortierung mit konstantem zusätzlichen Speicherplatzaufwand) konvertiert wird.

Alles, was ich (im Internet) finden kann, sind Seiten, auf denen steht "es ist zu komplex" oder "außerhalb des Geltungsbereichs dieses Textes".

Die einzigen bekannten Möglichkeiten zum Zusammenführen an Ort und Stelle (ohne zusätzlichen Speicherplatz) sind zu komplex, um auf ein praktisches Programm reduziert zu werden. ( von hier genommen )

Auch wenn es zu komplex ist, wie sieht das Grundkonzept aus, wie die Zusammenführungssortierung eingerichtet wird?

Laser
quelle
Schöne Frage, die ich mir selbst gestellt habe, als ich eine Frage von gestern durchgelesen
Chris Lercher
Hier wird eine ziemlich einfache Methode beschrieben: xinok.wordpress.com/2014/08/17/…
Branko Dimitrijevic

Antworten:

140

Knuth ließ dies als Übung (Band 3, 5.2.5). Es gibt In-Place-Zusammenführungssorten. Sie müssen sorgfältig umgesetzt werden.

Erstens ist eine naive In-Place-Zusammenführung wie hier beschrieben nicht die richtige Lösung. Die Leistung wird auf O (N 2 ) herabgestuft .

Die Idee ist, einen Teil des Arrays zu sortieren, während der Rest als Arbeitsbereich zum Zusammenführen verwendet wird.

Zum Beispiel wie die folgende Zusammenführungsfunktion.

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}  

Es nimmt die Anordnung xs, die zwei sortierten Subarrays werden als Bereiche dargestellt [i, m)und [j, n)jeweils. Der Arbeitsbereich beginnt ab w. Vergleichen Sie mit dem Standard-Zusammenführungsalgorithmus, der in den meisten Lehrbüchern angegeben ist. Dieser tauscht den Inhalt zwischen dem sortierten Unterarray und dem Arbeitsbereich aus. Infolgedessen enthält der vorherige Arbeitsbereich die zusammengeführten sortierten Elemente, während die im Arbeitsbereich gespeicherten vorherigen Elemente in die beiden Unterarrays verschoben werden.

Es gibt jedoch zwei Einschränkungen, die erfüllt sein müssen:

  1. Der Arbeitsbereich sollte innerhalb der Grenzen des Arrays liegen. Mit anderen Worten, es sollte groß genug sein, um ausgetauschte Elemente aufzunehmen, ohne einen Fehler außerhalb der Grenze zu verursachen.
  2. Der Arbeitsbereich kann mit einem der beiden sortierten Arrays überlappt werden. Es muss jedoch sichergestellt werden, dass keines der nicht zusammengeführten Elemente überschrieben wird.

Wenn dieser Zusammenführungsalgorithmus definiert ist, kann man sich leicht eine Lösung vorstellen, mit der die Hälfte des Arrays sortiert werden kann. Die nächste Frage ist, wie mit dem Rest des unsortierten Teils umgegangen werden soll, der im Arbeitsbereich gespeichert ist, wie unten gezeigt:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

Eine intuitive Idee besteht darin, eine weitere Hälfte des Arbeitsbereichs rekursiv zu sortieren, sodass nur 1/4 Elemente noch nicht sortiert wurden.

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

Der entscheidende Punkt in dieser Phase ist, dass wir die sortierten 1/4 Elemente B früher oder später mit den sortierten 1/2 Elementen A zusammenführen müssen.

Ist der Arbeitsbereich, der nur 1/4 Elemente enthält, groß genug, um A und B zusammenzuführen? Leider ist es nicht.

Die oben erwähnte zweite Einschränkung gibt uns jedoch einen Hinweis, dass wir sie ausnutzen können, indem wir den Arbeitsbereich so anordnen, dass er sich mit einem der beiden Unterarrays überlappt, wenn wir sicherstellen können, dass die Zusammenführungssequenz nicht überschrieben wird.

Anstatt die zweite Hälfte des Arbeitsbereichs zu sortieren, können wir auch die erste Hälfte sortieren und den Arbeitsbereich wie folgt zwischen die beiden sortierten Arrays einfügen:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

Dieser Aufbau ordnet effektiv die Überlappung des Arbeitsbereichs mit dem Subarray A an. Diese Idee wird in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. "Praktisches In-Place-Mergesort". Nordic Journal of Computing, 1996].

Das einzige, was noch übrig ist, ist, den obigen Schritt zu wiederholen, wodurch der Arbeitsbereich von 1/2, 1/4, 1/8, ... reduziert wird. Wenn der Arbeitsbereich klein genug wird (zum Beispiel nur noch zwei Elemente übrig), können wir Wechseln Sie zu einer einfachen Einfügungssortierung, um diesen Algorithmus zu beenden.

Hier ist die Implementierung in ANSI C basierend auf diesem Dokument.

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}

Wo wmerge zuvor definiert wurde.

Den vollständigen Quellcode finden Sie hier und die ausführliche Erklärung finden Sie hier

Diese Version ist übrigens nicht die schnellste Zusammenführungssortierung, da mehr Auslagerungsvorgänge erforderlich sind. Meinem Test zufolge ist es schneller als die Standardversion, die bei jeder Rekursion zusätzliche Leerzeichen zuweist. Es ist jedoch langsamer als die optimierte Version, bei der das ursprüngliche Array im Voraus verdoppelt und für die weitere Zusammenführung verwendet wird.

Larry LIU Xinyu
quelle
6
Knuth left this as an exercise (Vol 3, 5.2.5).bezieht sich auf ex. 13. [40] Implementieren Sie die vorgeschlagene interne Sortiermethode [am Ende dieses Abschnitts] und erstellen Sie zufällige Daten in O (N) Zeiteinheiten mit nur O (sqrt (N)) zusätzlichen Speicherplätzen. ? ( 40 zeigt ein ziemlich schwieriges oder langwieriges Problem an, das vielleicht als Semesterprojekt in Unterrichtssituationen geeignet ist. )
Graubart
4
Ich denke, dass die zeitliche Komplexität des in der penguin.ew-Site erwähnten In-Place-Algorithmus O ist (log n * n ^ 2). Da wir log n-Zusammenführungen haben und jede Zusammenführung in der Größenordnung von O (n ^ 2) liegt. Ist das nicht richtig?
Code4fun
1
Ist dieser Algorithmus noch stabil und in n log n Zeit?
Paul Stelian
1
@ PaulStelian - es ist nicht stabil. Elemente im Arbeitsbereich werden entsprechend den Bestellvorgängen für Elemente im sortierten Bereich neu angeordnet. Dies bedeutet, dass Arbeitsbereichselemente mit gleichen Werten neu angeordnet werden, sodass sie nicht mehr in ihrer ursprünglichen Reihenfolge sind.
rcgldr
1
@PaulStelian - Wiki hat einen Artikel zum Block-Merge-Sortieren , der, wie Sie kommentiert haben, stabil ist. Es funktioniert am besten, wenn mindestens 2 · sqrt (n) eindeutige Werte vorhanden sind, sodass sie neu angeordnet werden können, um Arbeitsbereiche eines Arrays bereitzustellen und stabil zu bleiben.
rcgldr
59

Inklusive des "großen Ergebnisses" beschreibt dieses Papier einige Varianten der In-Place-Merge-Sortierung (PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

In-Place-Sortierung mit weniger Zügen

Jyrki Katajainen, Tomi A. Pasanen

Es wird gezeigt, dass ein Array von n Elementen unter Verwendung von O (1) zusätzlichem Speicherplatz, O (n log n / log log n) Elementbewegungen und n log 2 n + O (n log log n) Vergleichen sortiert werden kann . Dies ist der erste In-Place-Sortieralgorithmus, der im schlimmsten Fall o (n log n) Bewegungen erfordert und gleichzeitig O (n log n) Vergleiche garantiert. Aufgrund der konstanten Faktoren ist der Algorithmus jedoch überwiegend von theoretischem Interesse.

Ich denke, das ist auch relevant. Ich habe einen Ausdruck davon herumliegen, der mir von einem Kollegen weitergegeben wurde, aber ich habe ihn nicht gelesen. Es scheint die grundlegende Theorie abzudecken, aber ich bin mit dem Thema nicht vertraut genug, um zu beurteilen, wie umfassend:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Optimale stabile Zusammenführung

Antonios Symvonis

Diese Arbeit zeigt, wie zwei Sequenzen A und B der Größen m und n, m ≤ n stabil mit O (m + n) -Zuweisungen, O (mlog (n / m + 1)) -Vergleichen und nur unter Verwendung einer Konstanten zusammengeführt werden können Menge zusätzlichen Platzes. Dieses Ergebnis stimmt mit allen bekannten Untergrenzen überein ...

Steve Jessop
quelle
12

Es ist wirklich nicht einfach oder effizient, und ich schlage vor, Sie tun es nur, wenn Sie es wirklich müssen (und Sie müssen es wahrscheinlich nicht tun, es sei denn, dies sind Hausaufgaben, da die Anwendungen des Inplace-Zusammenführens größtenteils theoretisch sind). Können Sie nicht stattdessen Quicksort verwenden? Quicksort wird mit ein paar einfacheren Optimierungen sowieso schneller sein und sein zusätzlicher Speicher ist O (log N) .

Wie auch immer, wenn Sie es tun müssen, dann müssen Sie. Folgendes habe ich gefunden: eins und zwei . Ich bin nicht mit der Inplace-Merge-Sortierung vertraut, aber es scheint, dass die Grundidee darin besteht, Rotationen zu verwenden, um das Zusammenführen von zwei Arrays ohne zusätzlichen Speicher zu erleichtern.

Beachten Sie, dass dies sogar langsamer ist als die klassische Zusammenführungssortierung, die nicht vorhanden ist.

IVlad
quelle
9
Quicksort ist nicht stabil. Das ist wirklich wichtig für viel Produktionscode.
Donal Fellows
7
quicksort kann stabil sein, und iirc merge sort ist nicht unbedingt stabil, wenn vorhanden
jk.
4
@jk: Quicksort ist nicht stabil; Die Geschwindigkeit ergibt sich daraus und Sie sollten nicht versuchen, etwas anderes zu behaupten. Es ist ein sehr guter Kompromiss. Ja, es ist möglich, den ursprünglichen Index mit dem Rest des Schlüssels zu verknüpfen, sodass Sie nie zwei Elemente gleich haben, was eine stabile Sortierung ergibt. Dies kostet zusätzlichen Platz (linear in der Anzahl der Elemente), da Sie die relative Reihenfolge der „äquivalenten“ Elemente ansonsten nicht beibehalten können, ohne auf zusätzliche Elementbewegungen zurückzugreifen, die die Leistung beeinträchtigen.
Donal Fellows
4
Quicksort hat auch einen O (n ^ 2) Worst Case für speziell gestaltete Eingaben
HoboBen
4
@DonalFellows: jk ist genau richtig; quicksort kann ohne zusätzliche Platzkosten stabil implementiert werden. Überprüfen Sie Wikipedia.
Rusty
10

Der entscheidende Schritt besteht darin, die Zusammenführung selbst in Kraft zu setzen. Es ist nicht so schwierig, wie diese Quellen ausmachen, aber Sie verlieren etwas, wenn Sie es versuchen.

Betrachten Sie einen Schritt der Zusammenführung:

[... Listen- sortiert ... | x ... Liste- A ... | y ... Liste- B ...]

Wir wissen , dass die sortierten Sequenz als alles weniger ist anders, dass x weniger als alles andere in A , und daß y kleiner ist als alles andere in B . In dem Fall, in dem x kleiner oder gleich y ist , bewegen Sie einfach Ihren Zeiger auf den Anfang von A auf eins. In dem Fall, in dem y kleiner als x ist , müssen Sie y über das gesamte A mischen, um es zu sortieren . Dieser letzte Schritt macht dies teuer (außer in entarteten Fällen).

Es ist im Allgemeinen billiger (insbesondere wenn die Arrays nur einzelne Wörter pro Element enthalten, z. B. einen Zeiger auf eine Zeichenfolge oder Struktur), etwas Zeit für Zeit auszutauschen und ein separates temporäres Array zu haben, zwischen dem Sie hin und her sortieren.

Donal Fellows
quelle
5
Ihre direkte Zusammenführung hat eine Worst-Case-Komplexität von O (m n), wobei m die Größe A und n die Größe B ist. Dies ist der Fall, wenn das erste Element in A größer als das letzte Element in B ist. Die Komplexität kann durch Hinzufügen von a auf O (k log (k) + m + n) verbessert werden , wobei k = min (m, n) ist Heap zwischen A und B. Dieser Heap sollte Elemente aus A enthalten, die größer sind als die verbleibenden Elemente in B, aber kleiner als die verbleibenden Elemente in A. Wenn A zuerst erschöpft ist, muss der Heap an das Ende von B verschoben werden. Andernfalls muss der Heap an den Anfang von A verschoben werden. Anschließend müssen die Heap-Elemente an Ort und Stelle entfernt und umgekehrt werden, um die Zusammenführung abzuschließen.
Valyala
2
@valyala Beachten Sie, dass bei Verwendung eines Heaps die Sortierung nicht mehr stabil ist. Wenn Sie einen Heap verwenden, können Sie auch die Heap-Sortierung anstelle der Zusammenführungssortierung verwenden.
Martinkunev
4

Ein Beispiel für eine pufferlose Zusammenführung in C.

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}

void mergesort(int* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       mergesort(v, h); mergesort(v+h, n-h);
       ip_merge_(v, v+h, v+n);
     }
}

Ein Beispiel für adaptives Mergesort (optimiert).

Fügt Support-Code und Änderungen hinzu, um die Zusammenführung zu beschleunigen, wenn ein Hilfspuffer beliebiger Größe verfügbar ist (funktioniert immer noch ohne zusätzlichen Speicher). Verwendet Vorwärts- und Rückwärtszusammenführung, Ringrotation, Zusammenführen und Sortieren kleiner Sequenzen und iteratives Zusammenführen.

#include <stdlib.h>
#include <string.h>

static int* copy_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (a != out)
       memcpy(out, a, count*sizeof(int));
    return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (b != out)
       memmove(out - count, a, count*sizeof(int));
    return out - count;
}

static int* merge_(const int* a1, const int* b1, const int* a2,
  const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *out++ = (*a1 <= *a2) ? *a1++ : *a2++;
    return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
  const int* a2, const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
    return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}

static unsigned int gcd_(unsigned int m, unsigned int n)
{
    while ( n != 0 )
     {
       unsigned int t = m % n;
       m = n;
       n = t;
     }
    return m;
}
static void rotate_inner_(const int length, const int stride,
  int* first, int* last)
{
    int* p, * next = first, x = *first;
    while ( 1 )
     {
       p = next;
       if ((next += stride) >= last)
          next -= length;
       if (next == first)
          break;
       *p = *next;
     }
    *p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       int n1 = c - a;
       int n2 = b - a;

       int* i = a;
       int* j = a + gcd_(n1, n2);

       for ( ; i != j; i++ )
          rotate_inner_(n1, n2, i, c);
     }
    return a + (c - b);
}

static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
 * @note faster for small sequences. */
{
    while ( a != b && b != c )
       if (*a <= *b)
          a++;
       else
        {
          int* p = b+1;
          while ( p != c && *p < *a )
             p++;
          rotate_(a, b, p);
          b = p;
        }
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
 * @note works with or without additional memory. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 <= n2 && n1 <= ts)
     {
       merge_(t, copy_(a, b, t), b, c, a);
     }
    else if (n2 <= ts)
     {
       merge_backward_(a, b, t, copy_(b, c, t), c);
     }
    /* merge without buffer. */
    else if (n1 + n2 < 48)
     {
       ip_merge_small_(a, b, c);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b, t, ts);
       ip_merge_(b, q, c, t, ts);
     }
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
  const int ts)
{
    int* p = a + cs*2;
    for ( ; p <= b; a = p, p += cs*2 )
       ip_merge_(a, a+cs, p, t, ts);
    if (a+cs < b)
       ip_merge_(a, a+cs, b, t, ts);
}

static void smallsort_(int* a, int* b)
/* insertion sort.
 * @note any stable sort with low setup cost will do. */
{
    int* p, * q;
    for ( p = a+1; p < b; p++ )
     {
       int x = *p;
       for ( q = p; a < q && x < *(q-1); q-- )
          *q = *(q-1);
       *q = x;
     }
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
    int* p = a + cs;
    for ( ; p <= b; a = p, p += cs )
       smallsort_(a, p);
    smallsort_(a, b);
}

static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
    int cs = 16;
    smallsort_chunk_(cs, v, v+n);
    for ( ; cs < n; cs *= 2 )
       ip_merge_chunk_(cs, v, v+n, t, ts);
}

static void* get_buffer_(int size, int* final)
{
    void* p = NULL;
    while ( size != 0 && (p = malloc(size)) == NULL )
       size /= 2;
    *final = size;
    return p;
}
void mergesort(int* v, int n)
{
    /* @note buffer size may be in the range [0,(n+1)/2]. */
    int request = (n+1)/2 * sizeof(int);
    int actual;
    int* t = (int*) get_buffer_(request, &actual);

    /* @note allocation failure okay. */
    int tsize = actual / sizeof(int);
    mergesort_lower_(v, n, t, tsize);
    free(t);
}
Johnny Cage
quelle
2
Hast du das geschrieben? Wie überwindet es die Schwierigkeiten, die in den anderen Antworten zum Ausdruck kommen? Was ist die Laufzeit?
Thomas Ahle
Dies ist aus meiner eigenen benutzerdefinierten Bibliothek angepasst , aber ich habe diese Algorithmen nicht erstellt, wenn Sie danach fragen. Das Wachstum ist O (n (log n) ^ 2) ohne Hilfsspeicher; O (n log n) mit vollem Puffer. Dies versucht eine praktische Implementierung zu sein und ist so strukturiert, dass konstituierende Algorithmen gezeigt werden.
Johnny Cage
Warum benötigen Sie eine Rekursion oder einen zusätzlichen Puffer, um zwei sortierte Listen zusammenzuführen? Ich denke, dies kann erreicht werden, indem die beiden Zeiger nach vorne bewegt und getauscht werden, wenn links größer als rechts ist.
Jack
3

Diese Antwort enthält ein Codebeispiel , das den im Artikel Praktisches In-Place-Zusammenführen beschriebenen Algorithmus implementiert von Bing-Chao Huang und Michael A. Langston beschrieben ist. Ich muss zugeben, dass ich die Details nicht verstehe, aber die gegebene Komplexität des Zusammenführungsschritts ist O (n).

Aus praktischer Sicht gibt es Hinweise darauf, dass reine In-Place-Implementierungen in realen Szenarien keine bessere Leistung erbringen. Beispielsweise definiert der C ++ - Standard std :: inplace_merge , was bedeutet , dass der Name eine direkte Zusammenführungsoperation impliziert.

Unter der Annahme, dass C ++ - Bibliotheken normalerweise sehr gut optimiert sind, ist es interessant zu sehen, wie sie implementiert werden:

1) libstdc ++ (Teil der GCC-Codebasis): std :: inplace_merge

Die Implementierung delegiert an __inplace_merge , wodurch das Problem umgangen wird , indem versucht wird, einen temporären Puffer zuzuweisen:

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

Andernfalls wird auf eine Implementierung ( __merge_without_buffer ) zurückgegriffen, die keinen zusätzlichen Speicher benötigt, aber nicht mehr in O (n) -Zeit ausgeführt wird.

2) libc ++ (Teil der Clang-Codebasis): std :: inplace_merge

Sieht ähnlich aus. Es delegiert an eine Funktion , die auch versucht, einen Puffer zuzuweisen . Je nachdem, ob genügend Elemente vorhanden sind, wird die Implementierung ausgewählt. Die Fallback-Funktion für konstanten Speicher heißt __buffered_inplace_merge .

Vielleicht ist sogar der Fallback noch O (n) -Zeit, aber der Punkt ist, dass sie die Implementierung nicht verwenden, wenn temporärer Speicher verfügbar ist.


Beachten Sie, dass der C ++ - Standard Implementierungen explizit die Freiheit gibt, diesen Ansatz zu wählen, indem die erforderliche Komplexität von O (n) auf O (N log N) verringert wird:

Komplexität: Genau N-1-Vergleiche, wenn genügend zusätzlicher Speicher verfügbar ist. Wenn der Speicher nicht ausreicht, werden O (N log N) Vergleiche durchgeführt.

Dies kann natürlich nicht als Beweis dafür angesehen werden, dass ein konstanter Raum an Ort und Stelle, der in O (n) Zeit verschmilzt, niemals verwendet werden sollte. Wenn es jedoch schneller wäre, würden die optimierten C ++ - Bibliotheken wahrscheinlich auf diese Art der Implementierung umsteigen.

Philipp Claßen
quelle
2

Dies ist meine C-Version:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}
Dylan Nissley
quelle
Beachten Sie, dass diese Implementierung im schlimmsten Fall (umgekehrtes Array) Θ (n ^ 2 log n) Zeit benötigt.
Martinkunev
1

Es gibt eine relativ einfache Implementierung der In-Place-Merge-Sortierung unter Verwendung der ursprünglichen Technik von Kronrod, jedoch mit einer einfacheren Implementierung. Ein bildliches Beispiel, das diese Technik veranschaulicht, finden Sie hier: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Es gibt auch Links zu detaillierteren theoretischen Analysen desselben Autors, die mit diesem Link verbunden sind.

Calbert
quelle
Dieser Link führt zu einem 403
Charlotte Tan
3
Link ist behoben. Die Dokumentation dort ist bis zur Stumpfheit kryptisch. Ich habe den Eindruck, dass es dort eine interessante Idee gibt, aber es wird kein Algorithmus vorgestellt, nur eine Reihe von Diagrammen und einige eher schwache Beschreibungen. Ich konnte die schwachen Beschreibungen nicht auf interessante Weise mit den Diagrammen verknüpfen, also gab ich auf.
Ira Baxter
-6

Ich habe gerade versucht, einen Zusammenführungsalgorithmus für die Zusammenführungssortierung in JAVA mithilfe des Einfügesortieralgorithmus zu verwenden. Dabei wurden die folgenden Schritte ausgeführt.
1) Es stehen zwei sortierte Arrays zur Verfügung.
2) Vergleichen Sie die ersten Werte jedes Arrays; und platzieren Sie den kleinsten Wert in das erste Array.
3) Platzieren Sie den größeren Wert mithilfe der Einfügesortierung (von links nach rechts durchlaufen) in das zweite Array.
4) Vergleichen Sie dann erneut den zweiten Wert des ersten Arrays und den ersten Wert des zweiten Arrays und machen Sie dasselbe. Wenn jedoch ein Austausch stattfindet, gibt es einen Hinweis darauf, dass der Vergleich der weiteren Elemente übersprungen wird, aber nur ein Austausch erforderlich ist.

Ich habe hier einige Optimierungen vorgenommen. um kleinere Vergleiche in der Einfügesortierung zu halten.
Der einzige Nachteil, den ich bei diesen Lösungen festgestellt habe, ist, dass die Array-Elemente im zweiten Array stärker ausgetauscht werden müssen.

z.B)

First___Array: 3, 7, 8, 9

Zweites Array: 1, 2, 4, 5

Dann bewirkt 7, 8, 9, dass das zweite Array alle seine Elemente jedes Mal um eins vertauscht (nach links bewegt), um sich im letzten zu platzieren.

Die Annahme, dass hier Gegenstände ausgetauscht werden, ist im Vergleich zum Vergleich zweier Gegenstände vernachlässigbar.

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

package sorting;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
    int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
    mergeSort(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));

    int[] array1 = {4, 7, 2};
    System.out.println(Arrays.toString(array1));
    mergeSort(array1, 0, array1.length -1);
    System.out.println(Arrays.toString(array1));
    System.out.println("\n\n");

    int[] array2 = {4, 7, 9};
    System.out.println(Arrays.toString(array2));
    mergeSort(array2, 0, array2.length -1);
    System.out.println(Arrays.toString(array2));
    System.out.println("\n\n");

    int[] array3 = {4, 7, 5};
    System.out.println(Arrays.toString(array3));
    mergeSort(array3, 0, array3.length -1);
    System.out.println(Arrays.toString(array3));
    System.out.println("\n\n");

    int[] array4 = {7, 4, 2};
    System.out.println(Arrays.toString(array4));
    mergeSort(array4, 0, array4.length -1);
    System.out.println(Arrays.toString(array4));
    System.out.println("\n\n");

    int[] array5 = {7, 4, 9};
    System.out.println(Arrays.toString(array5));
    mergeSort(array5, 0, array5.length -1);
    System.out.println(Arrays.toString(array5));
    System.out.println("\n\n");

    int[] array6 = {7, 4, 5};
    System.out.println(Arrays.toString(array6));
    mergeSort(array6, 0, array6.length -1);
    System.out.println(Arrays.toString(array6));
    System.out.println("\n\n");

    //Handling array of size two
    int[] array7 = {7, 4};
    System.out.println(Arrays.toString(array7));
    mergeSort(array7, 0, array7.length -1);
    System.out.println(Arrays.toString(array7));
    System.out.println("\n\n");

    int input1[] = {1};
    int input2[] = {4,2};
    int input3[] = {6,2,9};
    int input4[] = {6,-1,10,4,11,14,19,12,18};
    System.out.println(Arrays.toString(input1));
    mergeSort(input1, 0, input1.length-1);
    System.out.println(Arrays.toString(input1));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input2));
    mergeSort(input2, 0, input2.length-1);
    System.out.println(Arrays.toString(input2));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input3));
    mergeSort(input3, 0, input3.length-1);
    System.out.println(Arrays.toString(input3));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input4));
    mergeSort(input4, 0, input4.length-1);
    System.out.println(Arrays.toString(input4));
    System.out.println("\n\n");
}

private static void mergeSort(int[] array, int p, int r) {
    //Both below mid finding is fine.
    int mid = (r - p)/2 + p;
    int mid1 = (r + p)/2;
    if(mid != mid1) {
        System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ "  for p:"+p+"  r:"+r);
    }

    if(p < r) {
        mergeSort(array, p, mid);
        mergeSort(array, mid+1, r);
//      merge(array, p, mid, r);
        inPlaceMerge(array, p, mid, r);
        }
    }

//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
    int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
    int lengthOfRightArray = r - mid;

    int[] left = new int[lengthOfLeftArray];
    int[] right = new int[lengthOfRightArray];

    for(int i = p, j = 0; i <= mid; ){
        left[j++] = array[i++];
    }

    for(int i = mid + 1, j = 0; i <= r; ){
        right[j++] = array[i++];
    }

    int i = 0, j = 0;
    for(; i < left.length && j < right.length; ) {
        if(left[i] < right[j]){
            array[p++] = left[i++];
        } else {
            array[p++] = right[j++];
        }
    }
    while(j < right.length){
        array[p++] = right[j++];
    } 
    while(i < left.length){
        array[p++] = left[i++];
    }
}

//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
    int secondArrayStart = mid+1;
    int prevPlaced = mid+1;
    int q = mid+1;
    while(p < mid+1 && q <= r){
        boolean swapped = false;
        if(array[p] > array[q]) {
            swap(array, p, q);
            swapped = true;
        }   
        if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
            swap(array, p, secondArrayStart);
            swapped = true;
        }
        //Check swapped value is in right place of second sorted array
        if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
            prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
        }
        p++;
        if(q < r) {     //q+1 <= r) {
            q++;
        }
    }
}

private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
    int i = secondArrayStart;
    for(; i < array.length; i++) {
        //Simply swap till the prevPlaced position
        if(secondArrayStart < prevPlaced) {
            swap(array, secondArrayStart, secondArrayStart+1);
            secondArrayStart++;
            continue;
        }
        if(array[i] < array[secondArrayStart]) {
            swap(array, i, secondArrayStart);
            secondArrayStart++;
        } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
            break;
        }
    }
    return secondArrayStart;
}

private static void swap(int[] array, int m, int n){
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}
}
Kanagavelu Sugumar
quelle
3
Es ist sowohl O (n ^ 2) als auch sehr unlesbar (wegen der gelegentlichen Syntaxfehler und des inkonsistenten / schlechten Stils)
glaba