Hur sorterar jag en array?

#!/usr/bin/perl -w

use strict;

my @values = (
'foo52|52|bar52|111|Foobar|111|0',
'foo13|13|bar13|111|Foobar|111|0',
'foo22|22|bar22|111|Foobar|111|0',
'foo18|18|bar18|111|Foobar|111|0',
'foo6|6|bar6|111|Foobar|111|0',
'foo44|44|bar44|111|Foobar|111|0',
'foo18(2)|18|bar18(2)|111|Foobar|111|0',
'foo9|9|bar9|111|Foobar|111|0',
'foo15|15|bar15|111|Foobar|111|0',
'foo12|12|bar12|111|Foobar|111|0',
'foo2|2|bar2|111|Foobar|111|0',
'foo12(2)|12|bar12(2)|111|Foobar|111|0',
'foo9(2)|9|bar9(2)|111|Foobar|111|0',
);

# Sortera efter andra fältet m.h.a.
# "Schwartziansk transformering". :)
# Se 'perldoc -q sort'
my @sorted_values = map  { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map  { [ $_, ((/^[^|]*\|([^|]*)/)[0]) ] }
@values;

{
# Testblock för att se resultatet
local $, = "\n";
print "Innan sortering:\n";
print "------------------------------\n\n";
print @values;
print "\n\n------------------------------\n\n\n";
print "Efter sortering:\n";
print "------------------------------\n\n";
print @sorted_values;
print "\n\n------------------------------\n\n\n";
print "De tio första:\n";
print "------------------------------\n\n";
print @sorted_values[0..9];
print "\n\n------------------------------\n";
}

Nu kanske det kan hända att det andra fältet (som det sorteras på) kan ha samma värde i flera av posterna? I det här scriptet är det inte definierat vad som händer då, d.v.s. om t.ex. rad 10 har värdet 57 och rad 11 också har värde 57 så är det slumpen som avgör vilken som kommer med.

------------------
Robban < robban@lipogram.com >

Det funkade, men inte riktigt som jag ville. För det första sorterades de i fel ordning, jag vill ha det högsta först och lägsta sist. Sen så skriv resultatet inte till browser utan till någon fil. Skulle vara tacksam ifall det gick att fixa

------------------
/Emil Hesslow

För det första sorterades de i fel ordning, jag vill ha det högsta först och lägsta sist.

Bara att byta plats på $a->[1] och $b->[1]. Såhär:

my @sorted_values = map  { $_->[0] }
sort { $b->[1] <=> $a->[1] }
map  { [ $_, ((/^[^|]*\|([^|]*)/)[0]) ] }
@values;

Sen så skriv resultatet inte till browser utan till någon fil.

Ovanstående är själva sorteringsuttrycket. Om du har den osorterade arrayen i @values så får du den sorterade arrayen i @sorted_values. Den senare kan du därefter göra vad du vill med. Skriva den till en fil, eller vad du vill.

------------------
Robban < robban@lipogram.com >

Annars kan du ju titta i en algoritmbok och läsa om hur heaps (trappor) fungerar.

Om du har en trappa med 10 platser, och lägger in dina rader i trappan en och en, så kommer den ut sorterad som den skall. har en komplexitet på N log N om jag inte minns fel, dvs samma som quicksort.

om det är en stor databas det handlar om, >1 miljon poster eller så, så är detta en snabb och bra metod.

Peter Bredlöv
http://www.scorpiondata.com

Robban --> Det funkar. Sen undrar jag om du skulle kunna förklara hur sorteringen fungerar. Det skulle vara roligare om jag fattade vad som händer.

Peter_B --> Jag fattade ingenting om det du skrev men det kvittar för det handlar om max 200 rader så jag tror jag nöjer mig med Robbans sortering.

Tack igen Robban.

------------------
/Emil Hesslow

Kort beskrivet går det ut på att man skapar en temporär (namnlös) tvådimensionell array m.h.a. funktionen map().

Denna array är uppbyggd enligt följande:

[[Rad1 från orginalarrayen],[Det fält vi skall sortera på]],
[[Rad2 från orginalarrayen],[Det fält vi skall sortera på]],
o.s.v.

Det fält vi skall sortera på plockar vi ut m.h.a. ett reguljärt uttryck.

Sedan sorterar vi denna temporära array med perls inbyggda funktion sort().

I slutändan använder vi den temporära arrayen för att skapa arrayen @sorted_values som då kommer att innehålla orginalearrayen, sorterad på det vi plockade ut m.h.a. det reguljära uttrycket i början.

Koden skall läsas nerifrån och upp:

map  { [ $_, ((/^[^|]*\|([^|]*)/)[0]) ] } @values;

Här skapar vi den temporära, tvådimensionella arrayen. Resultatet av detta matar vi in i nästa led ...

sort { $b->[1] <=> $a->[1] }

... som sorterar på den "andra dimensionen" i denna array. Resultatet av denna sortering matar vi in i nästa led ...

map { $_->[0] }

... som skapar en temporär endimensionell array från den "första dimensionen" ur den tvådimensionella, sorterade, arrayen. Nu har vi alltså en sorterad, endimensionell array. Allt vi behöver göra är att stoppa undan den i en variabel, och det gör vi i nästa led.

my @sorted_values =

Detta är lite överkurs, och koden kan se rörig och obegriplig ut för den ovane. Samtidigt är sådana här "hack" lite av tjusningen med Perl tycker jag. Det är sådant som gör språket unikt gentemot andra språk. :)

För en djupare analys rekommenderas som sagt manualen:

'perldoc -q sort'

ftp://ftp.sunet.se/pub/lang/perl/CPAN/doc/FMTEYEWTK/sort.html

------------------
Robban < robban@lipogram.com >