Sortiermethoden in der Programmierung: Sortierung nach "Blase"

Sortierung durch eine Blase ist nicht nur nicht die schnellste Methode, darüber hinaus schließt es die Liste der langsamsten Arten der Bestellung. Allerdings hat es auch seine Vorteile. Also ist die Sortierung nach der Blasenmethode die logischste und natürlichste Lösung für das Problem, wenn man die Elemente in einer bestimmten Reihenfolge anordnen muss. Eine gewöhnliche Person, zum Beispiel, wird sie von Hand verwenden, einfach durch Intuition.

Woher kommt dieser ungewöhnliche Name?

Der Name der Methode wurde mit einer Analogie mit Luftblasen in Wasser erfunden. Das ist eine Metapher. So wie kleine Luftblasen an die Spitze steigen – weil ihre Dichte größer ist als jede Flüssigkeit (in diesem Fall – Wasser) und jedes Element des Arrays, je kleiner es ist, desto mehr geht es allmählich zum Anfang der Zahlenliste.

Beschreibung des Algorithmus

Die Blasensortierung erfolgt wie folgt:

• Der erste Durchgang: Die Elemente der Array von Zahlen werden in zwei genommen und werden auch paarweise verglichen. Wenn in einigen zwei der Elemente der erste Wert größer als der zweite ist, macht das Programm ihren Austausch von Plätzen;
• Daher ist die größte Zahl am Ende des Arrays. Während alle anderen Elemente, wie sie waren, in einer chaotischen Ordnung bleiben und eine weitere Sortierung erfordern;
• Daher ist ein zweiter Durchlauf notwendig: er wird analog zu dem vorherigen (bereits beschrieben) hergestellt und hat eine Anzahl von Vergleichen – minus eins;
• Bei dem Pass ist die Zahl drei Vergleiche eine weniger als die zweite und zwei, als die erste. Usw;
• Wir fassen zusammen, dass jeder Durchlauf (im Array eine bestimmte Zahl) minus (Anzahl der Pässe) Vergleiche hat.

Ein noch kürzerer Algorithmus des zukünftigen Programms kann wie folgt geschrieben werden:

• Das Array von Zahlen wird überprüft, bis zwei Zahlen gefunden werden, die zweite muss größer sein als die erste;
• Falsch in Bezug auf einander Elemente des Arrays befindet sich das Programm.

Pseudocode basierend auf dem beschriebenen Algorithmus

Die einfachste Implementierung ist wie folgt:

Vorgang Sortirovka_Puzirkom ;

Starten

Eine Schleife für j von nachalnii_index zu konechii_index ;

Eine Schleife für i von nachalnii_index zu konechii_index-1 ;

Wenn massiv [i]> massiv [i + 1] (das erste Element ist größer als das zweite), dann:

(Ändern Sie die Werte an Orten);

Das Ende

Natürlich verschärft hier die Einfachheit nur die Situation: Je einfacher der Algorithmus ist, desto mehr zeigt er alle Mängel. Zeitaufwendig ist auch für ein kleines Array zu groß (hier kommt die Relativität: Für die durchschnittliche Person kann die Zeitspanne klein erscheinen, aber im Programmierer jede Sekunde oder sogar Millisekunden auf dem Konto).

Es hat eine bessere Umsetzung gebracht. Zum Beispiel unter Berücksichtigung der Austausch von Werten in der Array an einigen Stellen:

Vorgang Sortirovka_Puzirkom ;

Starten

Sortivka = wahr;

Zyklus bei sortirovka = wahr;

Sortirovka = falsch;

Eine Schleife für i von nachalnii_index zu konechii_index-1 ;

Wenn massiv [i]> massiv [i + 1] (das erste Element ist größer als das zweite), dann:

(Wir ändern die Elemente an Orten);

Sortivka = wahr; (Angabe, dass der Austausch gemacht wurde).

Das Ende.

Nachteile der Methode

Der Hauptnachteil ist die Dauer des Prozesses. Wie lange funktioniert der Blasensortalgorithmus?

Die Ausführungszeit wird aus dem Quadrat der Anzahl der Zahlen im Array berechnet – das Endergebnis ist proportional dazu.

Mit dem Worst-Case-Szenario wird das Array so oft durchlaufen, wie es Gegenstände gibt, minus ein Wert. Dies ist, weil am Ende gibt es nur ein Element, das nichts zu vergleichen hat, und der letzte Durchlauf durch das Array wird eine nutzlose Aktion.

Darüber hinaus ist die Methode der Sortierung durch einfachen Austausch, wie es auch genannt wird, nur für Arrays von kleiner Größe wirksam. Große Datenmengen können nicht mit ihm verarbeitet werden: das Ergebnis ist entweder Fehler oder ein Programmabsturz.

Vorteile

Sortierung einer Blase ist sehr leicht zu verstehen. In den Lehrplänen der technischen Universitäten, beim Studium der Ordnung von Elementen eines Arrays, geht es zuerst. Die Methode ist sowohl in der Delphi-Programmiersprache (D (Delphi) als auch in C / C ++ (C / C plus plus) leicht zu implementieren, ein unglaublich einfacher Algorithmus für die ordnungsgemäße Anordnung von Pascal (Pascal). Die Sortierung mit einer Blase ist ideal für Anfänger.

Aufgrund von Mängeln wird der Algorithmus nicht für außerschulische Zwecke verwendet.

Ein klares Prinzip der Sortierung

Die Anfangsansicht des Arrays ist 8 22 4 74 44 37 1 7

Schritt 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Schritt 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Schritt 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Schritt 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Schritt 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Schritt 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Schritt 7 1 4 7 8 22 37 44 74.

Beispiel für die Sortierung durch eine Blase in Pascal

Beispiel:

Const kol_mas = 10;

Var massiv: array [1..kol_mas] von Integer;

A, b, k: ganzzahlig;

Fange an

Writeln ('input', kol_mas, 'elements of array');

Für a: = 1 zu kol_mas do readln (massiv [a]);

Für a: = 1 zu kol_mas-1 fange an

Für b: = a + 1 bis kol_mas fangen an

Wenn massiv [a]> massiv [b] dann beginnen

K: = massiv [a]; Massiv [a]: = massiv [b]; Massiv [b]: = k;

Ende;

Ende;

Ende;

Writeln ('nach sort');

Für a: = 1 zu kol_mas do writeln (massiv [a]);

Beenden

Beispiel für die Sortierung durch eine Blase in C (C)

Beispiel:

#include

#include

Int main (int argc, char * argv [])

{

Int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

Für (;;) {

Ff = 0;

Für (i = 7; i> 0; i -) {

Wenn (massiv [i] <massiv [i-1]) {

Swap (massiv [i], massiv [i-1]);

Ff ++;

}

}

Wenn (ff == 0) brechen;

}

Getch (); // Bildschirmverzögerung

Rückkehr 0;

}.