Sortiranje

[Kristijan]

Sortiranje je jedna od elegantnijih stvari u Perlu jer je sam algoritam
prepusten interpreteru dok mi mozemo jednostavno napisati,
@arr = sort @arr;
i @arr polje ce biti sortirano abecednim redom[1]
Da upotpunimo sliku, slijedece sortiranje je po funkcionalnosti identicno
gornjem, uz dodatak izricito definirane funkcije za usporedjivanje,
@arr = sort {$a cmp $b} @arr;
Objasnjenje:
1) $a i $b su globalne varijable koje se koriste kod sortiranja i nije ih
potrebno definirati prije upotrebe.
2) {$a cmp $b} je funkcija koja zbog "cmp" operatora vraca -1,0, ili 1 s
obzirom na to da li je $a manji, jednak, ili veci u odnosu na $b.
3) sort funkcija vraca sortiranu listu s obzirom na rezultate prethodno
opisane funkcije
Ako provirimo ispod haube, sortiranje ce ovako izgledati,

my @arr = qw/ide prva kamila ide druga kamila/;
@arr = sort { #5)sortirano polje
my $rez = $a cmp $b; #2)usporedi rijeci
print "'$a' cmp '$b' == $rezn"; #3)koje rijeci usporedjujemo?
$rez; #4)moze i "return $rez"
} @arr; #1)nesortirano polje
print "@arr = @arrn"; #6)ispisi @arr

Dakle, pocetna tocka je nesortirano polje(1) ciji elementi se uz pomoc
anonimne funkcije usporedjuju(2), zatim se ispisuje sto se usporedjivalo(3),
i na kraju funkcije ostavljamo sam rezultat usporedbe(4).
-- rezultat --

'ide' cmp 'prva' == -1
'kamila' cmp 'ide' == 1
'druga' cmp 'kamila' == -1
'ide' cmp 'ide' == 0
'ide' cmp 'prva' == -1
'prva' cmp 'kamila' == 1
'ide' cmp 'druga' == 1
'ide' cmp 'kamila' == -1
'ide' cmp 'kamila' == -1
'kamila' cmp 'kamila' == 0
'kamila' cmp 'prva' == -1
@arr = druga ide ide kamila kamila prva

Osim sortiranja rijeci, moguce je sortirati i brojeve za sto se koristi <=>
ili tzv. "space ship" operator. Za njega vrijedi isto sto i za cmp, osim sto
s njim sortiramo iskljucivo brojeve,
@arr = sort {$a <=> $b} @arr;
[1] najvjerojatnije engleskim abecednim redom, za detalje pogledati "perldoc
perllocale"
Primjeri,

#abecedno sortiranje unatrag
@arr = reverse sort @arr;
#isto kao i gore (sporije)
@arr = sort {$b cmp $a} @arr;
#sortiranje bez obzira na mala/velika slova
@arr = sort {uc($a) cmp uc($b)} @arr;
#Schwartizan transform, napredno sortiranje

U nekim slucajevima imamo polja ciji elementi se moraju dodatno obraditi da
bi bili spremni za usporedjivanje. Takva obrada moze biti prilicno zahtjevna
i ako ne kesiramo rezultate obrade, efikasnost naseg sortiranja ce opadati s
brojem elemenata koje sortiramo.
Zbog toga bi bilo idealno da zahtjevnu obradu elementa obavimo jedanput, a
ne svaki put kad treba odluciti izmedju $a i $b.
Ovako bi izgledao prethodni primjer ako primjenimo kesiranje,

my @arr = qw/ide Prva kAmila/;
my @temp = map [ $_, uc ], @arr; #1
@temp = sort { $a->[1] cmp $b->[1] } @temp; #2
@arr = map $_->[0], @temp; #3
#1 kreiramo @temp polje koje napunimo tako da za svaki element iz @arr
nastane novi element koji je referenca na polje, pa je onda,
@temp = (
# nulti, prvi
['ide', 'IDE'],
['Prva', 'PRVA'],
['kAmila', 'KAMILA'],
)
#2 sortiramo _reference_ iz @temp tako da usporedjujemo _prve_ elemente
('IDE', 'PRVA', 'KAMILA').
#3 konacno napunimo @arr sa _nultim_ elementima iz sortiranog @temp ('ide',
'kAmila', 'Prva')

Schwartizan transform je sortiranje koje funkcionira na isti nacin samo sto
ne koristimo pomocno @temp polje nego ulancane funkcije, pa je to onda,

@arr = map $_->[0], #3
sort { $a->[1] cmp $b->[1] } #2
map [ $_, uc ], @arr; #1

Ako postoji potreba za dodatno ubrzanje, sortiranje se moze ubrzati
pakiranjem elemenata koji se usporedjuju,
http://www.sysarch.com/perl/sort_paper.html

[marshall]

Odakle si ovo skidao?

[Kristijan]

nisam to od nikuda skidao, zašto?