Step 18 - Algorithmik 2

 

Sortieren - BubbleSort-Algorithmus

Im folgenden soll der Bubblesort-Algorithmus näher erläutert werden. Dieser Algorithmus sollte auch von einem Anfänger noch verstanden werden.
Zunächst mal ein Schaubild (ein s.g. Flussdiagram), das den Algorithmus allgemein beschreiben soll:
 
Nun in Delphi übersetzt, ergibt sich somit folgende Procedure:
procedure Bubble( zeilen : Array of String);
var
  i,k:Integer;
  speicher:String;

  procedure tausche(a, b : Integer);
  var
    speicher : String;
  begin
    speicher  := zeilen[a];
    zeilen[a] := zeilen[b];
    zeilen[b] := speicher;
  end;

begin
  // da ein dynamisches Array Null-basierend ist,
  // fangen wir bei 0 an und zählen insgesammt bis zum vorletzten
  for i:=0 to high(zeilen)-1 do
    for k:=i+1 to high(zeilen) do
      if zeilen[i]>zeilen[k] then
        tausche(i,k);
end;
 
gehen wir nun mal ein Array durch:
          0     1        2       3
arr['xyz','hallo','abc','fgh']
1. Lauf:
for i:=0 bis 2
  for k:=1 bis 3
    if 'xyz'>'hallo' stimmt da x in der ASCII-Tabelle einen größeren Index hat, als das h
       vertausche arr[0] mit arr[1]
    if beendet
  for geht weiter, da k<3
for k:=2
    if 'hallo'>'abc' stimmt...
       vertausche arr[0] mit arr[2]
    if beendet
  for geht weiter, da k<3
for k:=3
    if 'abc'>'fgh' stimmt nicht...
    if beendet
  for beendet
// momentan sieht das array so aus: arr['abc','hallo','xyz','fgh']
for geht weiter da i<2
for i:=1
  for k:=2 bis 3
    if 'hallo'>'xyz' stimmt nicht...
    if beendet
  for geht weiter da k<3
for k:=3
    if 'hallo'>'fgh' stimmt...
      vertausche arr[1] mit arr[3]
    if beendet
  for beendet
// momentan sieht das array so aus: arr['abc','fgh','xyz','hallo']
for geht weiter da i<2
for i:=2
  for k:=3 bis 3
    if 'xyz'>'hallo' stimmt...
      vertausche arr[2] mit arr[3]
    if beendet
  for beendet
for beendet
und nun:
arr['abc','fgh','hallo','xyz'];
Sortierung abgeschlossen ;-)
 
Wer sich hier eine weitere Erklärung wünscht, darf mir gerne via SocialMedia oder Mail schreiben. Das bewerte ich dann als "upvote" und investiere hier auch gerne noch mehr Zeit für euch ;)
 

Hinweis:

Außer Bubblesort gibt es noch viele andere Algorithmen, welche je nach verwendeter "Datenstruktur" und dem Dateninhalt wesentlich schneller sein können. Als Datenstruktur wurde hier ein Array genommen. Bei Quicksort oder Mergesort empfiehlt sich jedoch eine "doppelt verkettete Liste".
 

 

Externe Links zu SocialMedia-Seiten zu diesem Kapitel:

Diese Links sollen dazu dienen, Kommentare und Meinungen rund um dieses Kapitel wiedergeben zu können.
 
 
* Hinweis zu externen Links:
Bitte Haftungsausschluss beachten!
Ich übernehme weder Garantie, noch Gewährleistung, noch Haftung für Inhalte, die nach diesem Link folgen. Mit deinem Klick auf den Link verlässt du meine Website. Es öffnet sich in der Regel ein neuer Tab oder ein neues Fenster.