Wahl der Leser
Populäre Artikel
Verbesserte Blase. Blasensortierung. Vorlage verwenden
Bubble Sort ist der einfachste Sortieralgorithmus, der ausschließlich für Bildungszwecke verwendet wird. Für diesen Algorithmus gibt es keine praktische Anwendung, da er nicht effizient ist, insbesondere wenn ein großes Array sortiert werden muss. Zu den Vorteilen der Blasensortierung gehört die einfache Implementierung des Algorithmus.
Der Blasensortierungsalgorithmus läuft darauf hinaus, die Elemente des sortierten Arrays wiederholt zu durchlaufen. Beim Durchlaufen der Elemente des Arrays wird eine innere Schleife ausgeführt. Bei jedem Durchgang werden zwei benachbarte Elemente verglichen, und wenn die Reihenfolge falsch ist, werden die Elemente vertauscht. Die äußere Schleife wird ausgeführt, bis das Array sortiert ist. Somit steuert die äußere Schleife die Anzahl der Ausführungen der inneren Schleife. Wenn beim nächsten Durchlauf durch die Elemente des Arrays keine einzige Permutation vorgenommen wird, gilt das Array als sortiert. Um den Algorithmus besser zu verstehen, sortieren wir ein Array von beispielsweise 7 Zahlen mit der Blasenmethode (siehe Tabelle 1).
ursprüngliches Array: 3 3 7 1 2 5 0
| Iterationsnummer | Array-Elemente | Umordnungen | ||||||
|---|---|---|---|---|---|---|---|---|
| ref. Array | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
| 0 | 3 | 3 | FALSCH | |||||
| 1 | 3 | 7 | FALSCH | |||||
| 2 | 1 | 7 | 7>1, stimmt | |||||
| 3 | 2 | 7 | 7>2, stimmt | |||||
| 4 | 5 | 7 | 7>5, stimmt | |||||
| 5 | 0 | 7 | 7>0, wahr | |||||
| aktuell Array | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
| 0 | 3 | 3 | FALSCH | |||||
| 1 | 1 | 3 | 3>1, stimmt | |||||
| 2 | 2 | 3 | 3>2, stimmt | |||||
| 3 | 0 | 3 | 3>0, wahr | |||||
| 4 | 3 | 5 | FALSCH | |||||
| 5 | 5 | 7 | FALSCH | |||||
| aktuell Array | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
| 0 | 1 | 3 | 3>1, stimmt | |||||
| 1 | 2 | 3 | 3>2, stimmt | |||||
| 2 | 0 | 3 | 3>0, wahr | |||||
| 3 | 3 | 3 | FALSCH | |||||
| 4 | 3 | 5 | FALSCH | |||||
| 5 | 5 | 7 | FALSCH | |||||
| aktuell Array | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
| 1 | 2 | FALSCH | ||||||
| 0 | 2 | 2>0, wahr | ||||||
| 2 | 3 | FALSCH | ||||||
| 3 | 3 | FALSCH | ||||||
| 3 | 5 | FALSCH | ||||||
| 5 | 7 | FALSCH | ||||||
| aktuell Array | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
| 0 | 1 | 1>0, wahr | ||||||
| 1 | 2 | FALSCH | ||||||
| 2 | 3 | FALSCH | ||||||
| 3 | 3 | FALSCH | ||||||
| 3 | 5 | FALSCH | ||||||
| 5 | 7 | FALSCH | ||||||
| letztes Array | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
| Ende der Sortierung | ||||||||
Um das Array zu sortieren, reichten fünf Durchläufe der inneren Schleife for aus. Nach dem Start funktionierte die for-Schleife sechsmal, da das Array 7 Elemente enthält, sollte es eine Iteration (Wiederholung) der for-Schleife weniger geben. Bei jeder Iteration werden zwei benachbarte Array-Elemente verglichen. Wenn das aktuelle Array-Element größer als das nächste ist, vertauschen wir sie. Bis das Array sortiert ist, wird die innere Schleife ausgeführt und die Vergleichsoperation ausgeführt. Beachten Sie, dass bei jeder vollständigen Ausführung der for-Schleife mindestens ein Element des Arrays seinen Platz findet. Im schlimmsten Fall sind n-2 Durchläufe der inneren Schleife erforderlich, wobei n die Anzahl der Array-Elemente ist. Dies deutet darauf hin, dass die Blasensortierung für große Arrays äußerst ineffektiv ist.
Lassen Sie uns ein Programm entwickeln, in dem Sie zunächst die Größe eines eindimensionalen Arrays eingeben müssen. Anschließend wird das Array mit Zufallszahlen gefüllt und mithilfe der Blasensortierung sortiert.
// bu_sort.cpp: Definiert den Einstiegspunkt für die Konsolenanwendung. #include „stdafx.h“ #include
Das Ergebnis des Programms ist in Abbildung 1 dargestellt.
Jeder weiß sehr gut, dass aus der Klasse der Austauschsortierungen die schnellste Methode die sogenannte ist schnelle Sorte. Es werden Dissertationen darüber geschrieben, viele Artikel auf Habré sind ihm gewidmet und auf seiner Grundlage werden komplexe Hybridalgorithmen erfunden. Aber heute werden wir nicht darüber reden schnelle Sorte, und über eine andere Austauschmethode - die gute alte Blasensortierung und seine Verbesserungen, Modifikationen, Mutationen und Variationen.
Der praktische Nutzen dieser Methoden ist nicht so groß und viele Habra-Benutzer haben das alles in der ersten Klasse durchgemacht. Daher richtet sich der Artikel an diejenigen, die sich gerade für die Theorie der Algorithmen interessiert haben und erste Schritte in diese Richtung unternehmen.
Bild: Blasen
Heute werden wir über das Einfachste sprechen Sortierungen austauschen.
Wenn es jemanden interessiert, sage ich, dass es noch andere Kurse gibt - Auswahl sortieren, Sortieren durch Einfügen, Zusammenführen, sortieren, Verteilungssortierung, Hybridsorten Und parallele Sortierungen. Gibt es übrigens auch Esoterische Sortierungen. Hierbei handelt es sich um verschiedene gefälschte, im Grunde nicht realisierbare, komische und andere Pseudo-Algorithmen, über die ich im Hub „IT-Humor“ einige Artikel schreiben werde.
Mit der heutigen Vorlesung hat das aber nichts zu tun, es geht uns jetzt nur noch um einfache Tauschsortierungen. Es gibt auch viele Börsensortierungen selbst (ich kenne mehr als ein Dutzend), also schauen wir uns die sogenannten an Blasensortierung und einige andere, die eng damit verbunden sind.
Ich möchte Sie im Voraus warnen, dass fast alle der oben genannten Methoden sehr langsam sind und es keine eingehende Analyse ihrer zeitlichen Komplexität geben wird. Manche sind schneller, manche langsamer, aber grob gesagt können wir das im Durchschnitt sagen Ö(Nr. 2). Außerdem sehe ich keinen Grund, den Artikel mit Implementierungen in irgendwelchen Programmiersprachen zu überladen. Codebeispiele finden Interessenten ganz einfach auf Rosetta, Wikipedia oder anderswo.
Aber kehren wir zur Sortierung des Austauschs zurück. Die Reihenfolge erfolgt als Ergebnis der wiederholten sequentiellen Suche des Arrays und des Vergleichs von Elementpaaren miteinander. Wenn die verglichenen Elemente nicht relativ zueinander sortiert sind, tauschen wir sie aus. Die einzige Frage ist, wie genau das Array umgangen werden kann und auf welcher Grundlage Paare für den Vergleich ausgewählt werden sollen.
Beginnen wir nicht mit der Standard-Blasensortierung, sondern mit einem Algorithmus namens ...
Dumme Sorte
Sortieren ist wirklich dumm. Wir durchsuchen das Array von links nach rechts und vergleichen dabei die Nachbarn. Wenn wir auf ein Paar zueinander unsortierter Elemente stoßen, vertauschen wir sie und kehren zum Ausgangspunkt zurück, also ganz zum Anfang. Wir gehen das Array noch einmal durch und überprüfen es. Wenn wir wieder auf ein „falsches“ Paar benachbarter Elemente stoßen, tauschen wir die Plätze und beginnen von vorne. Wir machen weiter, bis das Array nach und nach sortiert ist.„Jeder Dummkopf kann so sortieren“, werden Sie sagen, und Sie werden völlig Recht haben. Aus diesem Grund wird das Sortieren als „dumm“ bezeichnet. In dieser Vorlesung werden wir diese Methode stetig verbessern und modifizieren. Jetzt hat er vorübergehende Schwierigkeiten Ö(Nr. 3), nachdem wir eine Korrektur vorgenommen haben, werden wir sie bereits bringen Ö(Nr. 2), dann beschleunigen wir es ein bisschen mehr, dann noch ein bisschen mehr, und am Ende werden wir es schaffen Ö(N Protokoll N) – und es wird überhaupt nicht „Quick Sort“ sein!
Lassen Sie uns eine einzige Verbesserung an der dummen Sortierung vornehmen. Nachdem wir während des Durchgangs zwei benachbarte unsortierte Elemente entdeckt und vertauscht haben, werden wir nicht zum Anfang des Arrays zurückkehren, sondern es ruhig bis zum Ende durchqueren.
In diesem Fall haben wir nichts weiter vor uns als das altbekannte...
Blasensortierung
Oder Sortieren nach einfachen Austauschvorgängen. Ein unsterblicher Klassiker des Genres. Das Funktionsprinzip ist einfach: Wir durchlaufen das Array vom Anfang bis zum Ende und tauschen dabei unsortierte benachbarte Elemente aus. Als Ergebnis des ersten Durchgangs „schwebt“ das maximale Element an die letzte Stelle. Jetzt durchlaufen wir erneut den unsortierten Teil des Arrays (vom ersten bis zum vorletzten Element) und ändern dabei die unsortierten Nachbarn. Das zweitgrößte Element wird an vorletzter Stelle stehen. In diesem Sinne werden wir den immer kleiner werdenden unsortierten Teil des Arrays durchqueren und die gefundenen Maxima bis zum Ende verschieben.Wenn wir nicht nur die Höchstwerte bis zum Ende, sondern auch die Mindestwerte an den Anfang schieben, dann gelingt es uns ...
Schüttlersortierung
Sie ist dieselbe Sortierung mischen, sie ist die Gleiche Cocktailsortierung. Der Prozess beginnt wie in einer „Blase“: Wir quetschen das Maximum nach ganz hinten heraus. Danach drehen wir uns um 180 0 und gehen in die entgegengesetzte Richtung, wobei wir nicht zum Maximum, sondern zum Minimum zurückrollen. Nachdem wir das erste und letzte Element im Array sortiert haben, machen wir erneut einen Salto. Nachdem wir mehrmals hin und her gegangen sind, beenden wir den Vorgang schließlich und landen in der Mitte der Liste.Die Shaker-Sortierung funktioniert etwas schneller als die Blasensortierung, da sowohl Maxima als auch Minima abwechselnd in den erforderlichen Richtungen durch das Array wandern. Die Verbesserungen liegen, wie man so sagt, auf der Hand.
Wie Sie sehen, geht das Verschieben schwerer (leichter) Elemente an die Enden des Arrays schneller, wenn Sie den Aufzählungsprozess kreativ angehen. Daher schlugen die Handwerker eine weitere nicht standardmäßige „Roadmap“ vor, um die Liste zu umgehen.
Gerade-ungerade Sortierung
Diesmal werden wir nicht über das Array hin und her huschen, sondern wieder auf die Idee eines systematischen Rundgangs von links nach rechts zurückkommen, aber nur einen größeren Schritt machen. Im ersten Durchgang werden Elemente mit einem ungeraden Schlüssel mit ihren Nachbarn auf gerader Basis verglichen (das 1. wird mit dem 2. verglichen, dann das 3. mit dem 4., das 5. mit dem 6. usw.). Dann vergleichen/verändern wir im Gegenteil „gerade“ Elemente mit „ungerade“. Dann wieder „ungerade-gerade“, dann wieder „gerade-ungerade“. Der Prozess stoppt, wenn nach zwei aufeinanderfolgenden Durchgängen durch das Array („ungerade-gerade“ und „gerade-ungerade“) kein einziger Austausch stattgefunden hat. Also haben sie es geklärt.In einer regelmäßigen „Blase“ drücken wir bei jedem Durchgang das aktuelle Maximum systematisch an das Ende des Arrays. Wenn man entlang gerader und ungerader Indizes springt, werden alle mehr oder weniger großen Elemente des Arrays in einem Durchlauf gleichzeitig um eine Position nach rechts verschoben. Auf diese Weise funktioniert es schneller.
Schauen wir uns den letzten an neu dekoriert* Für Sortuvannya Bulbashka** - Sortierung nach Kamm***. Diese Methode organisiert sehr schnell, Ö(Nr. 2) ist die größte Schwierigkeit. Im Laufe der Zeit haben wir im Durchschnitt Ö(N Protokoll N), und das Beste, Sie werden es nicht einmal glauben, Ö(N). Das heißt, ein sehr würdiger Konkurrent für alle Arten von „schnellen Sorten“, und das, wohlgemerkt, ohne den Einsatz von Rekursion. Allerdings habe ich versprochen, dass wir uns heute nicht weiter mit Reisegeschwindigkeiten befassen werden, also höre ich auf zu reden und gehe direkt zum Algorithmus über.
Es ist alles die Schuld der Schildkröten
Ein kleiner Hintergrund. Im Jahr 1980 erklärte Włodzimierz Dobosiewicz, warum die Blasensortierung und ihre Ableitungen so langsam funktionieren. Das liegt alles an den Schildkröten. „Schildkröten“ sind kleine Elemente, die sich am Ende der Liste befinden. Wie Sie vielleicht bemerkt haben, konzentrieren sich Blasensortierungen auf „Kaninchen“ (nicht zu verwechseln mit Babuschkins „Kaninchen“) – Elemente mit hohem Wert am Anfang der Liste. Sie bewegen sich sehr zügig auf die Ziellinie zu. Doch langsame Reptilien kriechen widerwillig zum Start. Sie können die Tortilla mit individuell gestalten Kämme.Bild: Schuldige Schildkröte
Kammsortierung
Bei „Bubble“, „Shaker“ und „Odd-Even“ werden beim Durchlaufen eines Arrays benachbarte Elemente verglichen. Die Grundidee des „Kamms“ besteht darin, zunächst einen ausreichend großen Abstand zwischen den zu vergleichenden Elementen zu nehmen und diesen Abstand bei der Anordnung des Arrays auf ein Minimum zu reduzieren. Auf diese Weise kämmen wir das Array und glätten es nach und nach zu immer saubereren Strähnen.Es ist besser, die anfängliche Lücke zwischen den verglichenen Elementen zu berücksichtigen, nicht irgendeinen, sondern einen speziellen Wert namens zu berücksichtigen reduzierender Faktor, dessen optimaler Wert etwa 1,247 beträgt. Erstens ist der Abstand zwischen den Elementen gleich der Größe des Arrays geteilt durch Reduktionsfaktor(Das Ergebnis wird natürlich auf die nächste ganze Zahl gerundet). Nachdem wir das Array mit diesem Schritt durchlaufen haben, teilen wir den Schritt erneut durch Reduktionsfaktor und gehen Sie die Liste noch einmal durch. Dies wird so lange fortgesetzt, bis die Indexdifferenz eins erreicht. In diesem Fall wird das Array mit einer regelmäßigen Blase sortiert.
Der optimale Wert wurde experimentell und theoretisch ermittelt Reduktionsfaktor:
Als diese Methode erfunden wurde, schenkten ihr um die Wende der 70er und 80er Jahre nur wenige Menschen Beachtung. Ein Jahrzehnt später, als die Programmierung nicht mehr den IBM-Wissenschaftlern und -Ingenieuren vorbehalten war, sondern sich bereits rasch großer Beliebtheit erfreute, wurde die Methode 1991 von Stephen Lacy und Richard Box wiederentdeckt, erforscht und populär gemacht.
Das ist eigentlich alles, was ich Ihnen über das Blasensortieren und andere, die es mögen, sagen wollte.
- Anmerkungen
* gekürzt ( ukrainisch) - Verbesserung
** Sortiert nach Glühbirne ( ukrainisch) – Blasensortierung
*** Sortierung nach Kamm ( ukrainisch) – Kammsortierung
Stichworte: Blasensortierung C, Blasensortierung, Blasensortierung eines zweidimensionalen Arrays
Blasensortierung
Und die Idee des Algorithmus ist sehr einfach. Wir gehen das Zahlenarray durch und überprüfen die Reihenfolge (die nächste Zahl muss größer und gleich der vorherigen sein). Sobald wir auf einen Verstoß gegen die Reihenfolge stoßen, tauschen wir sofort die Elemente aus und erreichen das Ende der Array, und beginnen Sie dann von vorne.
Sortieren Sie das Array (1, 5, 2, 7, 6, 3)
Wir gehen das Array durch, überprüfen die erste und die zweite Zahl, sie sind in aufsteigender Reihenfolge. Als nächstes kommt ein Verstoß gegen die Ordnung, wir tauschen diese Elemente aus
1, 2, 5, 7, 6, 3
Wir gehen das Array weiter durch, 7 ist mehr als 5, aber 6 ist weniger, also tauschen wir sie aus
1, 2, 5, 6, 7, 3
3 unterbricht die Reihenfolge, tauscht die Plätze mit 7
1, 2, 5, 6, 3, 7
Wir kehren zum Anfang des Arrays zurück und machen dasselbe
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Sie sagen, dass dies dem „Aufschweben“ von „leichteren“ Elementen wie Blasen ähnelt, weshalb der Algorithmus seinen Namen erhielt. void bubbleSort(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] >a) ( tmp = a[j]; a[j] = a; a = tmp; ) ) ) )
Dieser Algorithmus benötigt immer (n-1) 2 Schritte, unabhängig von den Eingabedaten. Selbst wenn das Array sortiert ist, wird es dennoch zweimal (n-1) durchlaufen. Darüber hinaus werden die bereits sortierten Daten noch einmal überprüft.
Nehmen wir an, wir müssen das Array nach 1, 2, 4, 3 sortieren
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Sobald die Elemente a und a vertauscht wurden, besteht keine Notwendigkeit mehr, diesen Abschnitt des Arrays zu durchlaufen. Berücksichtigen wir dies und überarbeiten wir den Algorithmus
Void bubbleSort2(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = i; j >0; j--) ( if (a[j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Eine weitere Implementierung
Void bubbleSort2b(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
In diesem Fall sind nur halb so viele Schritte erforderlich, aber das Problem beim Sortieren eines bereits sortierten Arrays bleibt bestehen: Sie müssen sicherstellen, dass die Funktion das sortierte Array einmal durchsucht. Dazu führen wir eine Flag-Variable ein: Sie wird weggelassen (Flag = 0), wenn das Array sortiert ist. Sobald wir auf einen Verstoß gegen die Reihenfolge stoßen, wird das Flag gesetzt (Flag = 1) und wir beginnen wie gewohnt mit der Sortierung des Arrays.
Void bubbleSort3(int *a, size_t size) ( size_t i; int tmp; char flag; do ( flag = 0; for (i = 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }
Auch in diesem Fall liegt die Komplexität in der Größenordnung von n 2 , bei einem sortierten Array erfolgt jedoch nur ein Durchlauf.
Lassen Sie uns nun den Algorithmus verbessern. Schreiben wir eine allgemeine Funktion zum Sortieren eines Arrays vom Typ „void“. Da der Typ der Variablen nicht bekannt ist, müssen Sie zusätzlich die Größe eines Array-Elements und die Vergleichsfunktion übergeben.
Int intSort(const void *a, const void *b) ( return *((int*)a) > *((int*)b); ) void bubbleSort3g(void *a, size_t item, size_t size, int (* cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; char flag; tmp = malloc(item); do ( flag = 0; for (i = 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }
Die Funktion sieht hässlich aus – oft wird die Adresse des aktuellen und vorherigen Elements berechnet. Lassen Sie uns hierfür einzelne Variablen hervorheben.
Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(item); do ( flag = 0; i = 1; prev = (char*)a; cur = (char*)prev + item; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }
Mit diesen Funktionen können Sie nun beispielsweise Arrays beliebiger Art sortieren
Void main() ( int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0;i< 10; i++) { printf("%d ", a[i]); } _getch(); }
Sortieren eines mehrdimensionalen Arrays
Das Sortieren eines statischen mehrdimensionalen Arrays unterscheidet sich im Wesentlichen nicht vom Sortieren eines eindimensionalen Arrays. Sie können die Tatsache ausnutzen, dass statische eindimensionale und mehrdimensionale Arrays im Speicher dieselbe Darstellung haben.
Void main() ( int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i = 0;i< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include
Zweitens können Sie das Array zunächst in ein eindimensionales Array verschieben, das eindimensionale Array sortieren und es dann wieder in ein zweidimensionales Array verschieben.
Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) ( size_t size = m*n, sub_size = n*item; size_t i, j , k; void *arr = malloc(size * item); char *p1d = (char*)arr; char *p2d = (char*)a; //Kopieren Sie ein zweidimensionales Array vom Typ „void“ in ein eindimensionales für (i = 0; i< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }
Wenn Sie von dieser Funktion verwirrt sind, verwenden Sie die getippte Funktion. Aufruf aus vorherigem Beispiel
Ordnen wir das Array von oben nach unten an, vom Nullelement bis zum letzten.
Die Idee der Methode: Der Sortierschritt besteht darin, das Array von unten nach oben zu durchlaufen. Unterwegs werden Paare benachbarter Elemente betrachtet. Wenn die Elemente eines bestimmten Paares in der falschen Reihenfolge sind, dann vertauschen wir sie.
Nachdem Null das Array durchlaufen hat, erscheint das leichteste Element oben – daher die Analogie mit einer Blase. Der nächste Durchgang erfolgt zum zweiten Element von oben, wodurch das zweitgrößte Element in die richtige Position gehoben wird ...
Wir durchlaufen den immer kleiner werdenden unteren Teil des Arrays, bis nur noch ein Element darin übrig bleibt. Hier endet die Sortierung, da die Reihenfolge aufsteigend ist.
Vorlage
Die durchschnittliche Anzahl von Vergleichen und Austauschen hat eine quadratische Wachstumsordnung: Theta(n 2), woraus wir schließen können, dass der Blasenalgorithmus sehr langsam und ineffektiv ist.
Allerdings hat es einen großen Vorteil: Es ist einfach und in jeder Hinsicht verbesserungswürdig. Was machen wir jetzt?
Betrachten wir zunächst eine Situation, in der auf keinem der Pässe ein Austausch stattgefunden hat. Was bedeutet das?
Das bedeutet, dass alle Paare in der richtigen Reihenfolge vorliegen, das Array also bereits sortiert ist. Und es macht keinen Sinn, den Vorgang fortzusetzen (insbesondere, wenn das Array von Anfang an sortiert wurde!).
Die erste Verbesserung des Algorithmus besteht also darin, sich zu merken, ob bei einem bestimmten Durchgang ein Austausch stattgefunden hat. Wenn nicht, terminiert der Algorithmus.
Der Verbesserungsprozess kann fortgesetzt werden, wenn man sich nicht nur an die Tatsache des Austauschs selbst, sondern auch an den Index des letzten Austauschs k erinnert. Tatsächlich: Alle Paare benachbarter Elemente mit Indizes kleiner als k befinden sich bereits in der erforderlichen Reihenfolge. Weitere Durchgänge können bei Index k enden, anstatt sich zu einer vorgegebenen Obergrenze i zu bewegen.
Eine qualitativ unterschiedliche Verbesserung des Algorithmus kann aus der folgenden Beobachtung gewonnen werden. Obwohl eine leichte Blase unten in einem Durchgang nach oben steigt, sinken schwere Blasen nur mit minimaler Geschwindigkeit: ein Schritt pro Iteration. Das Array 2 3 4 5 6 1 wird also in einem Durchgang sortiert, das Sortieren der Sequenz 6 1 2 3 4 5 erfordert jedoch 5 Durchgänge.
Um diesen Effekt zu vermeiden, können Sie die Richtung aufeinanderfolgender Durchgänge ändern. Der resultierende Algorithmus wird manchmal als „ Schüttlersortierung".
Vorlage
Wie stark hatten die beschriebenen Änderungen Auswirkungen auf die Wirksamkeit der Methode? Die durchschnittliche Anzahl der Vergleiche ist zwar gesunken, liegt aber weiterhin bei O(n 2), während sich die Anzahl der Austausche überhaupt nicht verändert hat. Die durchschnittliche (auch schlechteste) Anzahl der Operationen bleibt quadratisch.
Zusätzlicher Speicher ist offensichtlich nicht erforderlich. Das Verhalten der verbesserten (aber nicht der ursprünglichen) Methode ist ganz natürlich; ein fast sortiertes Array wird viel schneller sortiert als ein zufälliges. Die Blasensortierung ist stabil, aber die Schüttelsortierung verliert diese Qualität.
In der Praxis funktioniert die Blasenmethode trotz Verbesserungen leider zu langsam. Und deshalb wird es fast nie verwendet.
| In Verbindung stehende Artikel: | |
|
Erstellen einer Bootdiskette Partition Magic Das Programm parted magic ist nicht bootfähig
Parted Magic ist ein Programm für UNIX-Betriebssysteme, das entwickelt wurde... Die besten Programme zum Erstellen eines ISO-Disk-Images
Verwendung spezieller Programme. Ein virtuelles Abbild zu erstellen ist sehr... MacBook auf Werkseinstellungen zurücksetzen: Optionen und Anweisungen
Durch das Herunterfahren oder Neustarten Ihres Apple iMac wird der Inhalt des Speichers zurückgesetzt ... | |
