Die Webseiten der Fachschaft Informatik am ERG Saalfeld
Bubble-Sort
Bubble-Sort ist das einfachste Sortierverfahren, es ist "in-place" und die Anzahl der Elemente bleibt erhalten.
Beispiel:
Es werden nur die Vertauschungen angegeben und zwar sind die Elemente hervorgehoben, die gerade getauscht worden sind.
Das unsortierte Feld: |
2 5 9 8 1 5 2 4 |
Wir gehen jetzt das Feld der Reihe nach durch. Sind 2 Elemente in der falschen Reihenfolge, werden diese getauscht. |
2 5 8 9 1 5 2 4 |
|
2 5 8 1 9 5 2 4 |
|
2 5 8 1 5 9 2 4 |
|
2 5 8 1 5 2 9 4 |
Damit ist die größte Zahl an die letzte Stelle gekommen: |
2 5 8 1 5 2 4 9 |
Wir fangen wieder von vorn an. Das erste getauschte Paar ist: |
2 5 1 8 5 2 4 9 |
|
2 5 1 5 8 2 4 9 |
|
2 5 1 5 2 8 4 9 |
Damit ist die 2. größte Zahl an der vorletzten Stelle: |
2 5 1 5 2 4 8 9 |
Wir fangen wieder von vorn an. |
2 1 5 5 2 4 8 9 |
|
2 1 5 2 5 4 8 9 |
Jetzt ist die drittgrößte Zahl an der 3. Stelle von hinten. |
2 1 5 2 4 5 8 9 |
Wir fangen wieder von vorn an. |
1 2 5 2 4 5 8 9 |
|
1 2 2 5 4 5 8 9 |
|
1 2 2 4 5 5 8 9 |
Das Programm zum Sortieren mit Bubble-Sort sieht so aus:
Programm
use strict;
use warnings;
my @feld = (2, 5, 9, 8, 1, 5, 2, 4);
# Ausgabe des unsortierten Feldes
foreach my $element (@feld) {
print $element, ' ';
}
print "\n";
# sortieren mit Bubble-Sort
my $anzahl = scalar @feld;
my $help;
for (my $j = 0; $j < $anzahl - 1; $j++) {
for (my $i = 0; $i < $anzahl - $j - 1; $i++) {
if ($feld[$i] > $feld[$i+1]) {
$help = $feld[$i];
$feld[$i] = $feld[$i+1];
$feld[$i+1] = $help;
}
}
}
# Ausgabe des sortierten Feldes
foreach my $element (@feld) {
print $element, ' ';
}
print "\n";
__END__
Der Aufruf sah bei mir so aus:
Aufgaben
- Bringen Sie das Programm zum Laufen.
- Kommentieren Sie die Zeilen 13 bis 20 (das eigentliche Sortieren).
- Was bewirkt in der Zeile 16: "$i < $anzahl - $j - 1;" ?
- Ändern Sie das Programm so, dass die Elemente gewürfelt werden.
- Ändern Sie das Programm so, dass die Anzahl der Elemente in einer Variablen angegeben werden.
- Ändern Sie das Programm so, dass die Anzahl der Elemente als Parameter übergeben wird.
- Ändern Sie das Programm so, dass die gewürfelten Zahlen zwischen 100 und 900 liegen.
- Gestalten Sie die Ausgabe attraktiver.
Weblinks
- Wikipedia: Bubblesort
zurück
© ERG Saalfeld - Hans-Dietrich Kirmse 12.06.2015
|