wer immer strebend sich bemüht, den können wir erloesen (j.w.goethe)

Sortieren durch Auswahl (Selection Sort)

Eines der einfachen Sortierverfahren mit einer Laufzeit von O(n²), hier implementiert in Perl. Der Algorithmus lautet folgendermaßen:

  1. Initialisiere eine leere Folge, sie nimmt die sortierten Elemente auf.
  2. Solange die unsortierte Folge nicht leer ist, entnimm ihr das Minimum und hänge es die sortierte Folge an.
#!/usr/bin/perl

use strict;
use warnings;

my @array = (12,67,14,82,99,18,21,78,98,33,10);
my $first = 0;
my $last = $#array;

&PrintArray();
&SelectionSort();

sub SelectionSort {
  my ($min,$i,$j,$minindex) = undef;
  foreach $i ($first ... ($last - 1)) {
    $min = $array[$i];
    $minindex = $i;
    foreach $j (($i + 1) ... $last) {
      if ($array[$j] < $min) {
        $min = $array[$j];
        $minindex = $j;
      }
    }
    &Exchange($i,$minindex);
    &PrintArray();
  }
}


sub PrintArray {
  foreach my $i (0 ... $#array) {print $array[$i]," ";}
  print "\n";
}

sub Exchange {
  my ($i,$j) = @_;
  my $tmp = $array[$i]; 
  $array[$i] = $array[$j];
  $array[$j] = $tmp;
}

Startseite

Fotos und mehr ...