[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

Re: [PROGRAMMERING] dårlig quicksort i perl



"Martin Møller Skarbiniks Pedersen" <sslug@sslug> writes:

> sub SortBy {
>  my $type=shift;
>  my $key=shift;
>        my $count=shift;
>        my @sslug@sslug;
>
> [...snap...]

Må jeg gætte på at det du har snippet har været ækvivalent med noget
ala:

  my $pivot = $data[0]->{$key};

  my @upper = grep { $_->{$key} > $pivot } @data;
  my $ucount = @upper;

  my @middle = grep { $_->{$key} = $pivot } @data;
  my $mcount = @middle;

  my @lower = grep { $_->{$key} < $pivot } @data;
  my $lcount = @lower;


>        if($lcount>0) { @lower=SortBy($type,$key,$lcount,@lower); }
>        if($ucount>0) { @upper=SortBy($type,$key,$ucount,@upper); }
>
>        my $pos=0;
>        for($i=0;$i<$lcount;$i++) { $data[$pos++]=$lower[$i]; }
>        for($i=0;$i<$mcount;$i++) { $data[$pos++]=$middle[$i]; }
>        for($i=0;$i<$ucount;$i++) { $data[$pos++]=$upper[$i]; }
>        return @data; }



> Når jeg nu sidder at læse koden igen, tænker jeg på om det mon er en
> merge-sort istedet for.

Det er absolut en quicksort. Problemet med den er at den laver
forfærdelig meget kopiering af data. Bare at undlade linjen 'my
@sslug@sslug' og genererer @lower og @upper direkte fra @_ ville have
sparet en del plads.

Men den indbyggede sort-funktion er selvfølgelig bedre. 

//Makholm


 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2007-08-01, 02:01 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *