Sortieren durch Einfügen (Insertation 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 das erste Element und füge es an der richtigen Position in die sortierte Folge ein.
#!/usr/bin/perl

use strict;
use warnings;

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

&PrintArray();
&InsertationSort();

sub InsertationSort {
  my ($r,$i,$j) = undef;
  foreach $i (2 ... $last) {
    $r = $array[$i];
    $j = $i-1;
    while ($array[$j] > $r) {
      $array[$j+1] = $array[$j];
      $j = $j-1;
    }
    $array[$j+1] = $r;
    &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;
}

Alle Touren

Schneebergwege

Raxsteige

Geführte Touren

Perl

Literatur

Musik