Die Webseiten der Fachschaft Informatik am ERG Saalfeld


Selection-Sort

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

Beispiel:

Das unsortierte Feld:   2   5   9   8   1   5   2   4  

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

Das größte Element wurde mit dem letzten Element des aktuellen Feldes getauscht.   2   5   4   8   1   5   2   9  


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

Das größte Element im aktuellen Feld wurde mit dem letzten Element dieses Feldes getauscht.   2   5   4   2   1   5   8   9  


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

Hier wird nicht getauscht, weil (zufällig) das größte Element an der letzten Stelle im aktuellen Feld steht.   2   5   4   2   1   5   8   9  

usw.

Das größte Element im aktuellen Feld wurde wieder mit dem letzten Element dieses Feldes getauscht.   2   1   4   2   5   5   8   9  

 

Das größte Element im aktuellen Feld wurde wieder mit dem letzten Element dieses Feldes getauscht.   2   1   2   4   5   5   8   9  

 

Hier wird nicht getauscht, weil das größte Element an der letzten Stelle im aktuellen Feld steht.   2   1   2   4   5   5   8   9  

 

Das größte Element im aktuellen Feld wurde mit dem letzten Element dieses Feldes getauscht.   1   2   2   4   5   5   8   9  

fertig

 

Das Programm zum Sortieren mit Selection-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

# wir sortieren mit Selection-Sort
my $anzahl   = scalar @feld;
my $feldende = $anzahl;    # der Index wird gleich um 1 kleiner!
for (my $j = 0; $j < $anzahl; $j++) {
  # Initialisieren für einen Durchlauf
  $max    = -100000;
  $stelle = -1;
  $feldende--;

  # 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;
        }
  }

  # wir tauschen das groesste Element mit dem Element an der letzten Stelle
  $help  = $feld[$feldende];
  $feld[$feldende] = $max;
  $feld[$stelle]   = $help;
}

# 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. Kommentieren Sie die Zeilen 26 bis 41.
  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 100 und 700 liegen.

 

Weblinks

  1. Wikipedia: Selectionsort

 

zurück


© ERG Saalfeld   -   Hans-Dietrich Kirmse   16.06.2015