Geekly articles weekly

Ausgewogene Top-Down- und Bottom-Up-Fusion


Im letzten Artikel haben wir uns mit Relikt-Zusammenführungssorten vertraut gemacht (die hauptsächlich historisches Interesse hervorrufen). Was ist der Trend heute?

Um sich mit dem Konzept der Bestellung durch Fusionen vertraut zu machen, werden normalerweise ausgewogene Zusammenführungsalgorithmen verwendet. Der Begriff "Gleichgewicht" bedeutet, dass der Algorithmus das Array und seine Subarrays rekursiv in ungefähr gleiche Teile aufteilt. Heute schauen wir uns an, wie es in der Praxis aussieht.

Ein Funktionspaar ist für beide Methoden gleich. Wie auch immer, dieses "Down-Up", dieses "Up-Down" ist fast der gleiche Algorithmus, nur aus verschiedenen Blickwinkeln gezeigt.

Wir brauchen in der Tat die Zusammenführung von zwei Hälften des Segments zu einem Subarray. Die Hälften werden gleichzeitig in einem Array sortiert, die aktuellen Elemente in beiden Iterationen werden verglichen und das kleinere Element geht in das zweite Array:

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } }

Kopieren eines Segments von einem Array in ein anderes. Beide Implementierungen arbeiten auf zwei Arrays, die Daten müssen ständig vom Haupt- zum Hilfs- und umgekehrt geleitet werden:

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; }

Absteigende ausgewogene Fusion




Zuerst wird das gesamte Array genommen, wonach ein rekursiver Abstieg beginnt. Ein Array wird dichotomisiert, bis wir Subarrays eines Elements erreichen (die nach sich selbst sortiert sind). Dann beginnt die Rekursion mit dem umgekehrten Anstieg und verschmilzt die Subarrays auf dem Weg (deren Größe sich auf jeder Ebene verdoppelt).

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); }


Ausgewogene Aufwärtsfusion




Hier findet eine Iteration über das Array statt, während wir zuerst die benachbarten minimalen Arrays (von einem Element) nehmen und sie paarweise zusammenführen. Nachdem wir die sortierten Subarrays bei jedem Schritt verdoppelt haben, führen wir die Nachbarn erneut zusammen und fahren fort, bis wir das gesamte Array in der sortierten Form am Ausgang erhalten.

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } }

Im Allgemeinen ist eine Top-Down-Implementierung vorzuziehen, da zwei Arrays effizienter verwendet werden, wodurch die Rollen von "main / auxiliary" einfach ständig geändert werden. In der Upstream-Version ist Array A immer primär und Array B ist immer Hilfsarray. Infolgedessen müssen die Daten von B nach jeder Iteration vollständig an A zurückgegeben werden, was nicht zur Verbesserung der algorithmischen Komplexität beiträgt. Andererseits ist die Implementierung des Aszendenten einfacher, es gibt nicht einmal eine Rekursion.

Unausgeglichene Fusion


Aus dem Wort "Gleichgewicht" selbst geht eine Art Zuverlässigkeit und Stabilität hervor. Möglicherweise haben Sie sogar den Eindruck, dass ein guter Algorithmus ausgewogen sein muss. Und „Ungleichgewicht“ ist mit einer Art Wackelgefühl und Verzerrung verbunden. Sollte ein ausgeglichener nicht in jeder Hinsicht besser sein als ein unausgeglichener ?

In der Tat ist es schlimmer. Natürlich ist die Implementierung von Subarrays in gleiche Hälften (was unter Balance für Zusammenführungssorten zu verstehen ist) viel einfacher zu implementieren. Teilen Sie das Array in zwei Hälften und wenden Sie auf jede Hälfte eine Rekursion an. Tatsächlich ist diese Leichtigkeit der Hauptvorteil einer ausgewogenen Fusion vor einer unausgeglichenen.

In den folgenden Veröffentlichungen werden wir uns mit unausgeglichenen Methoden befassen. Sie sind deutlich schwieriger zu verstehen und umzusetzen. Daten für die nachfolgende Zusammenführung werden nicht gleichmäßig und gleichmäßig über Hilfsarrays verteilt, sondern in Übereinstimmung mit einer Reihe verallgemeinerter Fibonacci-Zahlen. Auf diese Weise können Sie leistungsstarke Ergebnisse erzielen, die für vereinfachte, ausgewogene Methoden nicht erreichbar sind.

Referenzen


Zusammenführen ( Google-translate ), Zusammenführen

Serienartikel:



Die nächsten Zusammenführungssortierungen sind jetzt in der AlgoLab-Anwendung verfügbar (für diejenigen, die Algorithmen mit dieser Excel-Anwendung studieren, aktualisieren Sie die Datei).

Arrays sind vorübergehend begrenzt - ihre Größe muss eine Zweierpotenz sein (aufgrund einiger Schwierigkeiten bei der Programmierung der Visualisierung). Wenig später können Arrays sortiert werden.

EDISON Software - Webentwicklung
Dieser Artikel wurde mit Unterstützung von EDISON Software verfasst, einem Unternehmen, das Cloud-Services verwendet, um eingebettete Software zu erstellen und mobile Anwendungen auf JAVA zu entwickeln .

Source: https://habr.com/ru/post/de432646/

More articles:


All Articles