Sortiranje poređenjem

Sortiranje skupa neobeleženih tegova pomoću težinske vage zahteva algoritam Sortiranja poređenjem.

Sortiranje poređenjem je jedan od algoritama sortiranja koji samo čita listu elemenata kroz jednu apstraktnu operaciju poređenja (često "manje ili jednako" operator ili trostruko poređenje) koji određuje koji od dva elementa treba prvi da se pojavi u krajnjoj sortiranoj listi. Jedini zahtev je to što operator poštuje dve osobine linearnog uređenja:

1. ako a ≤ b i b ≤ c onda a ≤ c (tranzitivnost)
2. za svako a i b, ili a ≤ b ili b ≤ a (trihotomija).

Ako je moguće da a ≤ b i b ≤ a; u ovom slučaju jedan ili drugi mogu doći prvi u sortiranu listu. U , u ovom slučaju ulazni redosled određuje sortirani redosled .

Metafora za razmišljanje o sortiranju poređenjem je da neko ima skup neobeleženih tegova i vagu (instrument). Cilj je da poređamo tegove po redu a bez ikakve informacije, osim toga što postavljamo dva tega na vagu i gledamo šta je teže (ili jednako).

Primeri

Kviksort sa listom brojeva. Horizontalne linije su pivot vrednosti.

Neki od najpoznatijih algoritama poređenja uključuju:

• Kviksort
• Hipsort
• Sortiranje spajanjem
• Intro sort
• Sortiranje umetanjem
• Sortiranje selekcijom
• Sortiranje mehurom
• Par-nepar sortiranje
• Koktel sortiranje
• Ciklično sortiranje
• Smutsort
• Timsort

Ograničenja performansi i prednosti različitih tehnika sortiranja

Postoje osnovna ograničenja za performanse sortiranja poređenjem. Sortiranje poređenjem mora da ima prosečnu donju granicu Ω(n log n) operacija poređenja , što je poznato i kao linearitmičko vreme. Ovo je posledica ograničenja informacija dostupnih kroz sama poređenja — ili, da ga stavi drugačije, u neodređene algebarske strukture potpuno uređenih skupova. U ovom smislu, sortiranje spajanjem, hipsort, i introsort su asimptotički optimalni u smislu broja poređenja koje moraju da odrade, iako ovo metrički zanemaruje druge operacije. Sortiranja koja nemaju poređenja (kao što su primer ispod) mogu da dostignu O(n) performansu korišćenjem drugih operacija, dopuštajući im da zaobiđu ovu donju granicu (pod pretpostavkom da su elementi konstantne veličine).

Primetite da sortiranje poređenjem može bite brže na nekim listama; mnogo adaptivnih sortiranja kao što je sortiranje umetanjem radi u O(n) vremenu na već sortiranoj ili polu-sortiranoj listi. Ω(n log n) donja granica prihvata samo slučajeve u kojima ulazna lista može biti u bilo kom mogućem redosledu.

Takođe primtite da u stvarnom životu brzina sortiranja zavisi i od mogućnost nekih algoritama da optimalno koriste relativno brzu keš memoriju, ili aplikacija može imati koristi od metoda za sortiranje u kojoj sortiran podaci počinju da se pojavljuju korisniku brže (i onda korisnikova brzina čitanja će biti ograničen faktor) za razliku od metoda sortiranja gde nije dostupan izlaz za prikazivanje sve dok cela lista ne bude sortirana.

Uprkos ovim ograničenjima, sortiranje poređenjem nudi primetnu praktičnu prednost koja kontroliše funkciju poređenja dozvoljavajući sortiranje veoma različitih tipova podataka i dobru kontrolu na sortiranoj listi. Na primer, obrtanje rezultata funkcije poređenja dozvoljava listi da bude obrnuto sortirana; i jednom se može sortirati lista n-torki u leksikografskom poretku tako što pravimo funkciju poređenja koja poredi svaki deo u sekvenci:

function NtorkaPoredjenje((leviA, leviB, leviC), (desniA, desniB, desniC))
    if leviA ≠ desniA
        return compare(leviA, desniA)
    else if leviB ≠ desniB
        return compare(leviB, desniB)
    else
        return compare(leviC, desniC)

Balansirana ternarna notacija omogućava da poređenje bude u jednom koraku, a rezultati budu "manje", "veće" ili "jednako".

Sortiranje poređenjem se generalno prilagođava mnogo lakše kompleksnom poretku kao što je poredak u brojevima sa pokretnim zarezom. Takođe, kad se fukcija poređenja jedno napiše, bilo koje sortiranje poređenjem se može iskoristiti bez modifikacije; sortiranja bez poređenja obično zajtevaju posebne verzije za svaki tip podataka.

Ova fleksibilnost, zajedno sa efikasnošću gorenavedenog algoritma sortiranja poređenjem na savremenim računarima, dovela je do velikog korišćenja ovog algoritma u raznim oblastima.

Alternative

Neki problemi sortiranja zahtevaju isključivo brže rešenje nego Ω(n log n) granica za Sortiranje poređenjem; primer je celobrojno sortiranje, gde su svi ključevi celi brojevi. Kada ključevi čine mali raspon, Sortiranje prebrojavanjem je primer algoritma koji radi u lenearnom vremenu. Ostali celobrojni algoritmi sortiranja, kao što je radiks sortiranje, nisu asimptotički brži od sortiranja poređenjem, ali u praksi mogu biti brži.

Problem sortiranja parova po njihovom zbiru ne podleže Ω(n² log n) granici ili (kvadratu rezultata uparivanja); najbolji poznati algoritam i dalje ima O(n² log n) vremensku složenost, ali samo O(n²) poređenja.

Broj proređenja neophodnih za sortiranje liste

n	$\lceil \log _{2}(n!)\rceil$	Minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30
13	33	34
14	37	38
15	41	42
16	45	45 or 46
19	57	58
22	70	71
n	$\lceil \log _{2}(n!)\rceil$	$n\log _{2}n-{\frac {n}{\ln 2}}$
10	22	19
100	525	521
1 000	8 530	8 524
10 000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Iznad: Poređenje donje granice $\lceil \log _{2}(n!)\rceil$ sa stvarni minimumom broja poređenja (od  A036604) koji je neophodan za sortiranje liste od n elemenata. Ispod: Pomoću Stirlingove aproksimacije, ova donja granica je optimizovana sa $n\log _{2}n-{\frac {n}{\ln 2}}$.

Broj poređenja koji ovaj algoritam zahteva povećanje u proporciji sa $n\log(n)$, gde $n$ je broj elemenata za sortiranje. Ova granica je asimptotički mala.

Data je lista različitih brojea (možemo pretpostaviti, pošto nas zanima analiza najgoreg mogućeg slučaja), postoji n faktorijel permutacija, i tačno jedana od tih predstavlja sortiranu listu. Algoritam za sortiranje mora dobiti dovoljno informacija iz poređenja da identifikuje tačnu permutaciju. Ako se algoritam uvek završava posle f(n) koraka, ne može da razlikuje više od 2^f(n) slučajeva zato što su ključevi različiti i svako poređenje ima samo dva moguća slučaja. Zato,

$2^{f(n)}\geq n!$, ili ekvivalentno $f(n)\geq \log _{2}(n!).$

Iz Stirlingove aproksimacije znamo da $\log _{2}(n!)$ je $\Omega (n\log _{2}n)$. Ovo potvrđuje tvrdnju za donju granicu.

Identična gornja granica sledi iz algoritama koji dostiže ovu granicu u najgorem slučaju.

Navedeni argument omogućuje apsolutnu, a ne samo asimptotičku donju granicu broja poređenja, tj. $\lceil \log _{2}(n!)\rceil$ poređenja. Ova donja granica je stvarno dobra (može se postići sa prostim algoritmom sortiranja spajanjem), ali je poznat da može biti netačan. Na primer, $\lceil \log _{2}(13!)\rceil =33$, ali najmanji broj poređenja za 13 elemenata je 34 (što je dokazano).

Određivanje tačnog broja poređenja potrebnih za sortiranje datog broja prijava, je računski težak problem čak i za malo n, i nije poznata jednostavna formula za rešenje. Za neke od nekoliko konkretnih vrednosti koje su izračunate, vidi  A036604.

Donja granica za prosečan broj poređenja

Slična granica važi i za prosečan broja poređenja. Pod pretpostavkom da

• su svi ključevi različiti, npr. svako poređenje će dati ili a>b ili a<b, i
• ulaz je slučajna permutacija, izabrana jedinstveno iz skupa svih mogućih permutacija n elemenata,

ne moguće je odrediti u kom redosledu je ulaz manji od log₂(n!) prosekom poređenja.

Ovo je najlakše primetiti pomoću koncepta teorije informacije. Entropija tako slučajne permutacije je log₂(n!) bitova. Pošto poređenje može dati samo dva rešenja, najveća količina informacije koju proizvede je 1 bit. Zato, posle k poređenja preostala entropija poređenja, s obzirom na rezultate poređenja je bar log₂(n!) - k bitova. Da bismo sortirali, neophodna je kompletna informacija, da bi preostala entropija bila 0. Iz toga sledi da k mora biti najmanje log₂(n!).

Primetite da se ovo razlikuje od najgore slučaja koji je dat gore iznad, smislu da ne dozvoljava zaokruživanje na najbliži ceo broj. Na primer, za n = 3, najgori slučak gornje granice je 3, prosek za donju granicu je oko 2.58, dok je najveća donja granica za prosečne slučajeve oko 2.67.

U ovakvim slučajevima više elemenata može imati isti ključ, ne postoji očigledna statistička interpretacija za "prosečan slučaj", tako da argument poput ovog iznad ne može biti primenjen bez pravljenja određenih pretpostavki o raspodeli ključeva.

Literatura

• Knuth, Donald (1997). „Minimum-Comparison Sorting”. The Art of Computer Programming. Volume 3: Addison-Wesley. str. 180–197. ISBN 978-0-201-89685-5.