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