PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Sortierung



DoktorByte
22.07.2008, 17:10
Ich fange gerade mit Perl an und versuche den Inhalt eines Arrays zu sortieren. Das klappt meistens auch, nur manchmal stimmen die letzten Stellen komischerweise nicht.
Ich weiß, dass es dafür eine Funktion gibt, aber ich möchte gerne wissen, wo bei mir der Fehler liegt.


#!/usr/bin/perl5.8.8

@array=();
for ($s=0; $s<50; $s++)
{
@array[$s]=(int rand(10));
}


$acount=@array;
$temp=0;
$vergleichswert1=0;
$vergleichswert2=0;

print "@array\n";

for ($i=0; $i<$acount; $i++)
{
for ($i2=0; $i2<$acount; $i2++)
{
if ($array[$vergleichswert1] >= $array[$vergleichswert2])
{
$vergleichswert2++;
}
else
{
$temp=$array[$vergleichswert2];
$array[$vergleichswert2]=$array[$vergleichswert1];
$array[$vergleichswert1]=$temp;
$temp=0;
}
}
$vergleichswert1++;
$vergleichswert2=0;
}
print "@array\n";

Danke schon mal im voraus

Added after 23 hours 58 minutes:

Hat keiner eine Idee ?

osiris
01.08.2008, 01:54
Hey,

Bin neu hier und mache auch viel in Perl.
Versuch das hier:


#!/usr/bin/perl

@array;

for($i=0;$i<50;$i++)
{
$array[$i]=(int rand(10));
}

$acount=@array;
print "@array\n\n";

for($i=0;$i<$acount;$i++)
{
for($j=0;$j<$acount;$j++)
{
if($array[$i]<$array[$j])
{
$temp=$array[$i];
$array[$i]=$array[$j];
$array[$j]=$temp;
}
}
}

print "@array\n";

Zur Erklärung:

Dein Fehler ist in dieser Schleife:




for ($i2=0; $i2<$acount; $i2++)
{
if ($array[$vergleichswert1] >= $array[$vergleichswert2])
{
$vergleichswert2++;
}
else
{
$temp=$array[$vergleichswert2];
$array[$vergleichswert2]=$array[$vergleichswert1];
$array[$vergleichswert1]=$temp;
$temp=0;
}
}

Die Variable $vergleichswert2 wird nur erhöht wenn nichts getauscht werden muss. Wenn z.B 10 mal getauscht werden muss ist die Schleife nach 49 durchläufen erst bei der Variable $array[39]. Da die Zählervariable ($i2) nach jedem Durchlauf erhöht wird bricht die Schleife ab obwohl sie noch nicht beim letzten Element ist.

Den Fehler kann man beheben indem man im else-Zweig entweder die Zeile
$vergleichswert2++;
oder die Zeile
$i2--;einfügt.

DoktorByte
04.08.2008, 14:21
Hallo,

danke für deine Antwort. Hatte ich erst gar nicht gesehen, da ich dachte, dass es eh keinen Interessiert. Ich habe meinen Fehler gefunden und ihn korrigiert. So funktioniert es:


#!/usr/bin/perl5.8.8

@array=();
for ($s=0; $s<10000; $s++)
{
@array[$s]=(int rand(100));
}

$acount=@array;
$temp=0;
$vergleichswert1=0;
$vergleichswert2=0;

print "@array\n";

for ($i=0; $i<$acount; $i++)
{
for ($i2=0; $i2<=$acount; $i2++)
{
if ($array[$vergleichswert1] >= $array[$vergleichswert2])
{
$vergleichswert2++;
}
else
{
$temp=$array[$vergleichswert2];
$array[$vergleichswert2]=$array[$vergleichswert1];
$array[$vergleichswert1]=$temp;
$temp=0;
}
}
$vergleichswert1++;
$vergleichswert2=0;
}
print "@array\n";

Dann habe ich mich noch an etwas anderem probiert, was um einiges schneller ist, und auch einwandfrei funktioniert:


#!/usr/bin/perl
#Programm funktioniert
use strict;

our @array = map { int(rand()*100) } (1..$ARGV[0]);
print "Zahlen unsortiert:\n @array\n";

quicksort(0, $#array);
sub quicksort
{
my ($links ,$rechts) = @_;
my $pivot = int ($array[($links + $rechts) / 2]);
my $l = $links;
my $r = $rechts;
my $i;
do {
while ($array[$l] < $pivot) { $l++; }
while ($array[$r] > $pivot) { $r--; }
if ($l <= $r) {
vertauschen($l, $r);
$l++;
$r--;
}
}while (($l <= $r));
if($links < $r) { quicksort($links, $r); }
if($l < $rechts) {quicksort($l, $rechts); }
}
sub vertauschen
{
my ($l, $r) = @_;
my $temp;

$temp = $array[$l];
$array[$l] = $array[$r];
$array[$r] = $temp;
}
print "Zahlen sortiert:\n @array\n";

In dem Sinne...
Dok