Implementieren Sie Insertion in C++ sortieren mit Stack oder Queue?

Classical Insertionsort-Algorithmus mit Array istImplementieren Sie Insertion in C++ sortieren mit Stack oder Queue?

void insertion_sort (int arr[], int length){ 
     int j, temp; 

    for (int i = 0; i < length; i++){ 
     j = i; 

     while (j > 0 && arr[j] < arr[j-1]){ 
       temp = arr[j]; 
       arr[j] = arr[j-1]; 
       arr[j-1] = temp; 
       j--; 
       } 
     } 
}

sollte es unter Verwendung von Stapel oder Warteschlange So implementiert?

Quelle

2016-10-26 Tomahawk

Ich wäre neugierig, wie Sie denken, dass Sie das tun würden. – gnasher729

Es ist nicht möglich, mit einem einzelnen Stapel zu sortieren. Es ist möglich, mit einer einzelnen Queue zu sortieren, etwa mit bubble sort, mit O (1) space, um ein einzelnes Element zu speichern. Mit 2 Stacks kann so etwas wie Bubble Sort implementiert werden. Mit 2 Warteschlangen oder 3 Stapeln kann eine Bottom-Up-Merge-Sortierung verwendet werden. Im Fall von 3 Stapeln ist eine Polyphase-Bottom-Up-Mischsortierung schneller, aber komplizierter. Da die Reihenfolge umgekehrt wird, wenn Daten von Stapel zu Stapel verschoben werden, muss das Programm verfolgen, ob es aufsteigende oder absteigende Sequenzen machen sollte, was zu der Komplikation beiträgt. – rcgldr

Wenn Sie einen Vektor verwenden, erhalten Sie die Leistung, mit der der gesamte Arbeitsspeicher zusammenhängend ist, aber die Leistung zu verlieren, weil Sie kopieren müssen. Wenn Sie eine verknüpfte Liste eines beliebigen Typs verwenden, gewinnen Sie, weil Sie nicht kopieren müssen, aber Sie verlieren, weil Ihr Speicher überall verstreut ist.

Als solche hängt dies von der Anzahl der Elemente, die sortiert werden, der Prozessor-Cache und wahrscheinlich eine ganze Reihe anderer Dinge.

Vorausgesetzt, dass dieser Sortieralgorithmus ist bekannt, dass langsam sein für jede Anzahl von N, ist die richtige Lösung, sich keine Sorgen über die Leistung überhaupt und verwenden Sie einfach std :: sort.

Quelle

2016-10-26 15:47:21 UKMonkey

Implementieren Sie Insertion in C++ sortieren mit Stack oder Queue?

Antwort

Verwandte Themen