Nicht rekursive Zusammenführungsart
https://stackoverflow.com/questions/1557894
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Kann jemand auf Englisch erklären, wie nicht rekursive Zusammenführungssortierung funktioniert?
Vielen Dank
Lösung
Schleifen Sie durch die Elemente und machen Sie jede benachbarte Gruppe von zwei Sortierungen, indem Sie die beiden bei Bedarf austauschen.
Jetzt, der sich mit Gruppen von zwei Gruppen (zwei beliebige, höchstwahrscheinlich benachbarte Gruppen, aber Sie können die ersten und letzten Gruppen verwenden) in eine Gruppe verschmelzen Gruppe von 4. Jetzt haben Sie nur Gruppen von 4 plus einen möglichen Rest. Durch die Verwendung einer Schleife um die vorherige Logik wird alles wieder in Gruppen von 4. Arbeiten, bis es nur eine Gruppe gibt.
Andere Tipps
Nicht rekursive Zusammenführungssortierung funktioniert unter Berücksichtigung der Fenstergrößen von 1,2,4,8,16..2^n über das Eingangsarray. Für jedes Fenster ('k' im Code unten) werden alle benachbarten Fensterpaare in einen temporären Raum verschmolzen und dann wieder in das Array eingesetzt.
Hier ist meine einzelne Funktion, C-basierte, nicht rekursive Zusammenführungssorte. Eingang und Ausgabe sind in 'a'. Temporäre Speicherung in 'B'. Eines Tages möchte ich eine Version haben, die an Ort war:
float a[50000000],b[50000000];
void mergesort (long num)
{
int rght, wid, rend;
int i,j,m,t;
for (int k=1; k < num; k *= 2 ) {
for (int left=0; left+k < num; left += k*2 ) {
rght = left + k;
rend = rght + k;
if (rend > num) rend = num;
m = left; i = left; j = rght;
while (i < rght && j < rend) {
if (a[i] <= a[j]) {
b[m] = a[i]; i++;
} else {
b[m] = a[j]; j++;
}
m++;
}
while (i < rght) {
b[m]=a[i];
i++; m++;
}
while (j < rend) {
b[m]=a[j];
j++; m++;
}
for (m=left; m < rend; m++) {
a[m] = b[m];
}
}
}
}
Übrigens ist es auch sehr einfach zu beweisen, dass dies O (n log n) ist. Die äußere Schleife über der Fenstergröße wächst als Leistung von zwei, so dass K log n Iterationen hat. Während es viele Fenster gibt, die von der inneren Schleife zusammen sind, decken alle Fenster für ein bestimmtes k genau das Eingangsarray ab, sodass die innere Schleife o (n) ist. Kombinieren von inneren und äußeren Schleifen: o (n)*o (log n) = o (n log n).
Zitieren von Algorithmiker:
Bottom-up-Zusammenführungssortierung ist eine nicht rekursive Variante der Zusammenführungsart, in der das Array nach einer Abfolge von Pässen sortiert wird. Während jedes Durchgangs ist das Array in Größe der Größe unterteilt m. (Anfänglich, M = 1). Alle zwei benachbarten Blöcke werden zusammengeführt (wie bei normaler Zusammenführungsart), und der nächste Pass wird mit einem zweimal größeren Wert von hergestellt m.
Sowohl rekursive als auch nicht rekursive Zusammenführungssorten haben die gleiche Zeitkomplexität von O (NLog (n)). Dies liegt daran, dass beide Ansätze Stack auf die eine oder andere Weise verwenden.
Im nicht rekursiven Ansatz definiert und verwendet der Benutzer/Programmierer Stack
Im rekursiven Ansatz wird Stack intern vom System verwendet, um die Rückgabeadresse der Funktion zu speichern, die rekursiv bezeichnet wird
Der Hauptgrund, warum Sie einen nicht rekursiven Mergesort verwenden möchten, besteht darin, einen Überlauf von Rekursionsstapeln zu vermeiden. Ich versuche zum Beispiel, 100 Millionen Datensätze, jeweils etwa 1 kByte in Länge (= 100 Gigabyte), in alphanumerischer Reihenfolge zu sortieren. Eine Sortierung (n^2) würde 10^16 Operationen dauern, dh es würde Jahrzehnte dauern, bis es mit 0,1 Mikrosekunde pro Vergleichsbetrieb ausgeführt wird. Eine Verschlusssortierung (n log (n)) dauert weniger als 10^10 Operationen oder weniger als eine Stunde, um mit der gleichen Betriebsgeschwindigkeit zu laufen. In der rekursiven Version von Mergesort führt die 100-Millionen-Element-Sortierung jedoch zu 50 Millionen rekursiven Aufrufen des Mergesorts (). Bei einigen hundert Bytes pro Stapelrekursion überläuft dies den Rekursionsstapel, obwohl der Vorgang leicht in den Heap -Speicher passt. Durch das Durchführen der Zusammenführungssortierung mit einem dynamisch zugewiesenen Speicher auf dem Heap- Ich verwende den Code von Rama Hoetzlein oben, aber ich verwende dynamisch zugewiesene Speicher auf dem Haufen, anstatt den Stapel zu verwenden- ich kann meine 100 Millionen Datensätze mit dem sortieren Nicht rekursive Zusammenführungsart und ich überlaufe den Stapel nicht. Ein geeignetes Gespräch für die Website "Stack Overflow"!
PS: Danke für den Code, Rama Hoetzlein.
PPS: 100 Gigabyte auf dem Haufen? !! Nun, es ist ein virtueller Haufen auf einem Hadoop -Cluster, und der Mergesort wird parallel auf mehreren Maschinen implementiert, die die Last teilen ...
Ich bin neu hier. Ich habe die Rama Hoetzlein -Lösung verändert (danke für die Ideen). Meine Zusammenführungsart verwendet nicht die letzte Kopierschleife. Außerdem fällt es bei der Einfügungssorte zurück. Ich habe es auf meinem Laptop mit einem Benchmarking und es ist das schnellste. Noch besser als die rekursive Version. Übrigens ist es in Java und sortiert von absteigender Reihenfolge bis hin zu aufsteigender Ordnung. Und natürlich ist es iterativ. Es kann multithread gemacht werden. Der Code ist komplex geworden. Wenn jemand interessiert ist, schauen Sie bitte einen Blick darauf.
Code:
int num = input_array.length;
int left = 0;
int right;
int temp;
int LIMIT = 16;
if (num <= LIMIT)
{
// Single Insertion Sort
right = 1;
while(right < num)
{
temp = input_array[right];
while(( left > (-1) ) && ( input_array[left] > temp ))
{
input_array[left+1] = input_array[left--];
}
input_array[left+1] = temp;
left = right;
right++;
}
}
else
{
int i;
int j;
//Fragmented Insertion Sort
right = LIMIT;
while (right <= num)
{
i = left + 1;
j = left;
while (i < right)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
left = right;
right = right + LIMIT;
}
// Remainder Insertion Sort
i = left + 1;
j = left;
while(i < num)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
// Rama Hoetzlein method
int[] temp_array = new int[num];
int[] swap;
int k = LIMIT;
while (k < num)
{
left = 0;
i = k;// The mid point
right = k << 1;
while (i < num)
{
if (right > num)
{
right = num;
}
temp = left;
j = i;
while ((left < i) && (j < right))
{
if (input_array[left] <= input_array[j])
{
temp_array[temp++] = input_array[left++];
}
else
{
temp_array[temp++] = input_array[j++];
}
}
while (left < i)
{
temp_array[temp++] = input_array[left++];
}
while (j < right)
{
temp_array[temp++] = input_array[j++];
}
// Do not copy back the elements to input_array
left = right;
i = left + k;
right = i + k;
}
// Instead of copying back in previous loop, copy remaining elements to temp_array, then swap the array pointers
while (left < num)
{
temp_array[left] = input_array[left++];
}
swap = input_array;
input_array = temp_array;
temp_array = swap;
k <<= 1;
}
}
return input_array;
Nur für den Fall, dass jemand noch in diesem Thread lauert ... Ich habe den nicht rekursiven Zusammenführungs-Sortieralgorithmus von Rama Hoetzlein angepasst, um doppelte verknüpfte Listen zu sortieren. Diese neue Sortierung ist stabil und vermeidet eine zeitkostspielige Listenabteilung, die sich in anderen Implementierungen für verknüpfte List-Zusammenführungen befindet.
// MergeSort.cpp
// Angus Johnson 2017
// License: Public Domain
#include "io.h"
#include "time.h"
#include "stdlib.h"
struct Node {
int data;
Node *next;
Node *prev;
Node *jump;
};
inline void Move2Before1(Node *n1, Node *n2)
{
Node *prev, *next;
//extricate n2 from linked-list ...
prev = n2->prev;
next = n2->next;
prev->next = next; //nb: prev is always assigned
if (next) next->prev = prev;
//insert n2 back into list ...
prev = n1->prev;
if (prev) prev->next = n2;
n1->prev = n2;
n2->prev = prev;
n2->next = n1;
}
void MergeSort(Node *&nodes)
{
Node *first, *second, *base, *tmp, *prev_base;
if (!nodes || !nodes->next) return;
int mul = 1;
for (;;) {
first = nodes;
prev_base = NULL;
//sort each successive mul group of nodes ...
while (first) {
if (mul == 1) {
second = first->next;
if (!second) {
first->jump = NULL;
break;
}
first->jump = second->next;
}
else
{
second = first->jump;
if (!second) break;
first->jump = second->jump;
}
base = first;
int cnt1 = mul, cnt2 = mul;
//the following 'if' condition marginally improves performance
//in an unsorted list but very significantly improves
//performance when the list is mostly sorted ...
if (second->data < second->prev->data)
while (cnt1 && cnt2) {
if (second->data < first->data) {
if (first == base) {
if (prev_base) prev_base->jump = second;
base = second;
base->jump = first->jump;
if (first == nodes) nodes = second;
}
tmp = second->next;
Move2Before1(first, second);
second = tmp;
if (!second) { first = NULL; break; }
--cnt2;
}
else
{
first = first->next;
--cnt1;
}
} //while (cnt1 && cnt2)
first = base->jump;
prev_base = base;
} //while (first)
if (!nodes->jump) break;
else mul <<= 1;
} //for (;;)
}
void InsertNewNode(Node *&head, int data)
{
Node *tmp = new Node;
tmp->data = data;
tmp->next = NULL;
tmp->prev = NULL;
tmp->jump = NULL;
if (head) {
tmp->next = head;
head->prev = tmp;
head = tmp;
}
else head = tmp;
}
void ClearNodes(Node *head)
{
if (!head) return;
while (head) {
Node *tmp = head;
head = head->next;
delete tmp;
}
}
int main()
{
srand(time(NULL));
Node *nodes = NULL, *n;
const int len = 1000000; //1 million nodes
for (int i = 0; i < len; i++)
InsertNewNode(nodes, rand() >> 4);
clock_t t = clock();
MergeSort(nodes); //~1/2 sec for 1 mill. nodes on Pentium i7.
t = clock() - t;
printf("Sort time: %d msec\n\n", t * 1000 / CLOCKS_PER_SEC);
n = nodes;
while (n)
{
if (n->prev && n->data < n->prev->data) {
printf("oops! sorting's broken\n");
break;
}
n = n->next;
}
ClearNodes(nodes);
printf("All done!\n\n");
getchar();
return 0;
}
Bearbeitet 2017-10-27: Ein Fehler, der sich auf ungerade nummerierte Listen auswirkt
