Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Insertion-Sort

Insertion-Sort ist "in-place" und die Anzahl der Elemente bleibt erhalten.

Beispiel:

Wir suchen in dem Feld das größte Element.

Da das größte Element an der letzten Stelle steht, betrachten wird dieses Element nicht mehr. Die nun betrachtete aktuelle Liste ist um ein Element kleiner.

Die beiden größten Elemente stehen an der richtigen Stelle. Das zu betrachtende Feld = aktuelles Feld wird wieder um ein Element kleiner.

usw.

fertig

Das Programm zum Sortieren mit Insertion-Sort sieht so aus:

Programm

use strict;
use warnings;

# wir erstellen/wuerfeln ein Feld
my @feld = ();
foreach ( 1 .. 100 ) {
  push @feld, int(rand(300)) + 200;
}

# Ausgabe des unsortierten Feldes
foreach my $element (@feld) {
  print $element, ' ';
}
print "\n";

# Variablen für das Tauschen
my $help;           # Hilfsvariable für das Tauschen
my $max;           # der Wert des groessten Elements
my $stelle;         # die Stelle des groessten Elements

my $anzahl   = scalar @feld; # Anzahl der Elemente
my $feldende = $anzahl;       # der Index wird gleich um 1 kleiner!

for (my $j = 0; $j < $anzahl-1; $j++) {
  # Initialisieren für einen Durchlauf
  $max    = -100;   # da wir grossen Wert suchen, hier kleiner Wert
  $stelle = -1;       # ein Wert, den es im Feld nicht gibt
  $feldende--;       # Index vom Feldende 1 kleiner

  # wir suchen in dem Feld von $feld[0] bis $feld[$feldende] die groesste Zahl
  for (my $i = 0; $i <= $feldende; $i++) {
    if ($feld[$i] > $max) {
          $max    = $feld[$i];
          $stelle = $i;
        }
  }

  # dieses Element aus der Liste heraus nehmen = löschen (den Wert haben wir)
  splice(@feld,$stelle,1);  # an der Stelle $stelle wird ein Element geloescht

  # dieses Element an der letzten Stelle der aktuellen Liste einfuegen
  splice(@feld,$feldende,0,$max);
}

# Ausgabe des sortierten Feldes
foreach my $element (@feld) {
  print $element, ' ';
}
print "\n";

__END__

Der Aufruf sah bei mir so aus:

Aufgaben

1. Bringen Sie das Programm zum Laufen.
2. Informieren Sie sich über den Befehl "splice".
3. Ändern Sie das Programm so, dass die Anzahl der Elemente als Parameter übergeben wird.
4. Ändern Sie das Programm so, dass die gewürfelten Zahlen zwischen 200 und 600 liegen.

Weblinks

1. Wikipedia: Insertionsort

zurück