Gambas: Sortieren

zurück zu Gambas

Sortierverfahren werden bei Datenbanken, Tabellen, Arrays und vielem mehr gebraucht. Einige einfache Sortierverfahren werden im Folgenden beschrieben.

Ripplesort

Sie haben eine Zahlenfolge 13,12,15,11,14 . Diese Zahlen wollen Sie in aufsteigender Reihenfolge ordnen, so daß die kleinste Zahl am Anfang und die größte am Ende steht.

Wie das geht zeigt folgendes Programm. Es nutzt ein Array ( siehe Gambas: Arrays) und mehrere Hilfsvariablen . Dieses Array wird mehrfach durchsortiert, bis die Reihenfolge stimmt.

Sie brauchen eine Form und einen Commandbutton, um das Programm in Gang zu bringen.

' Gambas class file
ar AS Integer[]
PUBLIC SUB Form_Open()
'schon beim Öffnen der Form wird der Array mit lauter Nullen gefüllt.
x AS Integer
ar = NEW Integer[]
ME.Text = "Sortieren"
FOR x = 0 TO 4
 ar.Add(Str(0))
NEXT
END
PUBLIC SUB Button1_Click()
c AS Integer 
j AS Integer 
n AS Integer 
y AS Integer 
element AS Integer 
y = 0
n = ar.count 
ar[0] = 13
ar[1] = 12
ar[2] = 15
ar[3] = 11
ar[4] = 14
REPEAT 
c = 0
 FOR j = 0 TO n - 2
   PRINT j,y,ar[0],ar[1],ar[2],ar[3],ar[4]
    IF ar[j] > ar[j + 1] THEN 
     y = ar[j] 
     ar[j] = ar[j + 1]
     ar[j + 1] = y 
     c = 1
    ENDIF 
 NEXT 
UNTIL c = 0 
END

Die Ausgabe im Direktfenster schaut dann so aus:

 PRINT j,y,ar[0],ar[1],ar[2],ar[3],ar[4]

0      0       1       2       3       4       5

0       0       13      12      15      11      14
1	13	12	13	15	11	14
2	13	12	13	15	11	14
3	15	12	13	11	15	14
0	15	12	13	11	14	15
1	15	12	13	11	14	15
2	13	12	11	13	14	15
3	13	12	11	13	14	15
0	13	12	11	13	14	15
1	12	11	12	13	14	15
2	12	11	12	13	14	15
3	12	11	12	13	14	15
0	12	11	12	13	14	15
1	12	11	12	13	14	15
2	12	11	12	13	14	15
3	12	11	12	13	14	15

Das Sortierverfahren steckt in der Repeat until Schleife . Darin steckt eine for next Schleife und darin steckt wieder eine Vertauschung mit if then . Das ist schon ein bißchen schwer zu kapieren. Mit der ausführlichen Ausgabe im Direktfenster kann man das Sortieren genau verfolgen. Man kann den Array ändern und andere Zahlen einfügen. Dann kann man wieder zuschauen, wie die Sortierung abläuft. Der Kern ist eine Vertauschung zweier benachbarter Zahlen, wenn die linke Zahl größer als die rechte ist. Der Rest der Zeile bleibt stehen. Dann erfolgt ein neuer Durchlauf der For Next Schleife , bei dem nichts passiert da in Position ar[1] des Arrays jetzt 13 steht und 13 < 15 ist. ( das Array beginnt mit der zahl 0 und hört mit n-1 auf, wenn es n Elemente hat. Beim nächsten Durchlauf der For Next Schleife wird die Position ar[2] = 15 mit ar[3] = 11 verglichen . Da 15 > 11 wird getauscht. Dann ist die For next Schleife das erste Mal zu Ende, da j = 3 = n-2 und die Repeatschleife wird ein zweites mal durchlaufen an, denn der Hilfsparameter c zeigt einen stattgefundenen Tausch an. Und so geht das immer weiter bis c = 0 , d.h. keine Vertauschung mehr nötig war.

Ripplesort mit Zufallszahlen

Das folgende Programm ist vom obigen abgeleitet. Erst werden per Zufall 5 Zahlen zwischen 1 und 5 erzeugt. Diese werden dann sortiert. Sie brauchen eine Textarea und 2 Commandbuttons, um das Programm in Gang zu bringen.

' Gambas class file
ar AS Integer[]
PUBLIC SUB Form_Open()
'schon beim Öffnen der Form wird der Array mit lauter Nullen gefüllt.
x AS Integer
ar = NEW Integer[]
ME.Text = "Sortieren"
FOR x = 0 TO 4
  ar.Add(Str(0))
NEXT
END
PUBLIC SUB Button1_Click()
x AS Integer 
r AS Integer 
element AS Integer 
txt AS String
z AS Integer 
txt = ""
'der Array wird komplett auf Null gestellt
FOR x = 0 TO 4
 ar[x] = 0 
NEXT
Randomize() 
FOR x = 0 TO 4
 r = Int(Rnd(1,6))
ar[x] = r
NEXT 
x = 0 
FOR EACH element IN ar 
PRINT x,element
txt = txt & x & "  " & element & Chr(10) 
 x = x + 1
NEXT
textarea1.Text = txt 
END
PUBLIC SUB Button2_Click()
c AS Integer 
j AS Integer 
n AS Integer 
y AS Integer 
element AS Integer 
txt AS String 
y = 0
n = ar.count 
REPEAT 
c = 0
FOR j = 0 TO n - 2
  PRINT j,y,ar[0],ar[1],ar[2],ar[3],ar[4]
  IF ar[j] > ar[j + 1] THEN 
    y = ar[j] 
    ar[j] = ar[j + 1]
    ar[j + 1] = y 
    c = 1
  ENDIF 
NEXT 
UNTIL c = 0 
FOR EACH element IN ar 
txt = txt & element & Chr(10) 
NEXT
textarea1.Text = textarea1.Text & txt 
END

Zahlenliste beliebiger Länge durchsortieren

Im folgenden Beispiel wird der Ripplesort-Algorithmus zum Sortieren einer beliebig langen Werteliste benutzt. Sie brauchen 2 Textareas und 2 Commandbuttons, um das Programm in Gang zu bringen.

Code:

' Gambas class file
PUBLIC SUB Button1_Click()
c AS Integer 
j AS Integer 
n AS Integer 
y AS Variant
DIM Liste AS String[]
element AS String 
txt AS String 
text AS String 
text = Textarea1.Text
liste = Split(text,Chr(10))
y = 0
n = liste.length
REPEAT 
c = 0
 FOR j = 0 TO n - 2
   'PRINT j,y,liste[0],ar[1],ar[2],ar[3],ar[4]
   IF Val(liste[j]) > Val(liste[j + 1]) THEN 
     y = Val(liste[j]) 
     liste[j] = liste[j + 1]
     liste[j + 1] = Str(y) 
     c = 1
   ENDIF 
 NEXT 
UNTIL c = 0 
FOR EACH element IN liste 
txt = txt & Str(element) & Chr(10) 
NEXT
'PRINT txt
textarea2.Text = ""
textarea2.Text = txt
END
PUBLIC SUB Button2_Click()
'Beispielliste
 textarea1.Text = "114,3"
 textarea1.Text = textarea1.Text & Chr(10) & "135,7"
 textarea1.Text = textarea1.Text & Chr(10) & "104,8"
 textarea1.Text = textarea1.Text & Chr(10) & "118,5"
 textarea1.Text = textarea1.Text & Chr(10) & "125,7"
 textarea1.Text = textarea1.Text & Chr(10) & "121,4"
 textarea1.Text = textarea1.Text & Chr(10) & "122,4"
 textarea1.Text = textarea1.Text & Chr(10) & "96,8"
 textarea1.Text = textarea1.Text & Chr(10) & "118,9"
 textarea1.Text = textarea1.Text & Chr(10) & "120"
 textarea1.Text = textarea1.Text & Chr(10) & "112,2"
 textarea1.Text = textarea1.Text & Chr(10) & "127,9"
 textarea1.Text = textarea1.Text & Chr(10) & "122,8"
 textarea1.Text = textarea1.Text & Chr(10) & "128,9"
 textarea1.Text = textarea1.Text & Chr(10) & "120,3"
END