Quicksort

Quicksort (batzuetan ordenazio azkarra edo partizio-truke bidezko ordenazioa deitzen dena) hainbat balio ordenatzeko algoritmo eraginkorrenetako bat da. Tony Hoare informatikari britainiarrak 1959an garatu eta 1961ean argitaratu zuen, ohiko ordenatze-algoritmo bat da oraindik. Ongi inplementatzen denean, beste algoritmo lehiakide nagusiak (merge-sort eta heapsort) baino bizpahiru aldiz azkarragoa izan daiteke.

Quicksort zatitu eta irabazi erako algoritmo bat da. Ordenatu behar diren elementuen artean pibot ("pivot") elementu bat hautatuz eta gainerako elementuak bi azpi-bektoretan zatituz funtzionatzen du, batetik pibota baino txikiagoak direnak eta bestetik handiagoak direnak. Gero azpi-bektore bietako bakoitza era berean ordenatzen da, modu errekurtsiboan. Hori lekuan bertan (in-place) egin daitekeenez, memoria gehigarri txikiak behar ditu ordenaketa egiteko.

Quicksort konparazio bidezko ordenazioa da, hau da, edozein motatako elementuak ordenatu ditzake "gutxiago baino" erako erlazio bat (formalki, 'hurrenkera osoa', 'erabateko ordena') definituta baldin badago. Quicksort-en ezarpen eraginkorrak ez dira orden egonkorrak, hau da, orden berdineko elementuen orden erlatiboa ez da mantentzen.

Quicksort-en analisi matematikoak erakusten du ezen algoritmoak, batez beste, O(n log n) konparaketak egiten dituela n elementu ordenatzeko. Kasurik okerrenean, O(n2) alderaketak egiten ditu, nahiz eta kasu hori arraroa izan.

Historia 
Quicksort algoritmoa 1959an asmatu zuen Tony Hoarek Sobietar Batasunean, Moskuko Estatu Unibertsitateko ikasle bisitari gisa. Garai hartan, Hoarek Laborategi Fisiko Nazionalerako itzulpen automatikozko proiektu batean lan egiten zuen. Itzulpen-prozesuaren urrats batean, errusierazko esaldiko hitzak ordenatu behar zituen geroago errusiera-ingeles hiztegi batean hitz guztiak bilatu baino lehen, hiztegiko hitzak aldez aurretik zeuden alfabetikoki ordenatuta zinta magnetiko batean. Bere lehen ideia, txertatze-ordenazioa, motela izango zela onartu ondoren, berehala bururatu zitzaion Quicksort-en ideia. Partiziorako Mercury Autocode-n programa bat idatzi zuen, baina ezin zuen berdin egin ordenatu gabeko segmentuen zerrenda kontabilizatzeko. Ingalaterrara itzultzerakoan, Shellsort ordenaziorako kode berria idazteko eskatu zitzaion bere lan berrian. Algoritmo azkarrago bat ezagutzen zuela bere nagusiari aipatu zionean nagusiak apustu egin zion ezetz. Nagusiak, azkenean, onartu behar izan zuen apustua galdu zuela. Geroago, ALGOL lengoaia ezagututa, errekurtsioak zuen ahalmenaz baliatuta Quicksort algoritmo osoa inplementatu ahal izan zuen, eta kodea Communications of the Association for Computing Machinery aldizkarian argitaratu zuen. Garaiko informatikako aldizkari nagusia zen argitaratzeko aukera eman ziona.

Quicksort-ek onarpen zabala lortu zuen, Unix- en, adibidez, liburutegiko sort azpierrutina lehenetsi gisa agertuz. Hori dela eta, C liburutegi estandarreko qsort azpierrutinari eman zuen izena, baita Javaren inplementaziokoari ere.

Robert Sedgewick-en tesia (1975) mugarritzat jotzen da Quicksort-en garapenean. Pibota hautatzeko hainbat eskemaren (Samplesort, eta Van Emden-ek egindako partizio moldatzailea) analisiarekin lotutako arazo ireki asko konpondu zituen, baita espero diren konparaketa eta swap kopurua ere. Jon Bentley-k eta Doug McIlroy-k hainbat hobekuntza sartu zituzten programazio-liburutegietan erabiltzeko; besteak beste, elementu berdinak jorratzeko teknika eta bederatziko pseudomediana gisa ezagutzen den pibot eskema , non bederatzi elementuren lagina hiru taldetan banatzen den, eta ondoren hiru taldeetako hiru medianen mediana aukeratzen da. Bentley-k Nico Lomutori egotzitako beste partizio-eskema sinple eta trinkoago bat deskribatu zuen Programming Pearls liburuan. Geroago, Bentley-k idatzi zuen Hoare-ren bertsioa erabili zuela urtetan, baina inoiz ez zuela benetan ulertu, baina Lomuto-ren bertsioa ulergarriagoa zela, zuzena zela frogatzea nahikoa erraza zen. Bentley-k, "idatzi dudan kode ederrena" gisa deskribatu zuen Quicksort saiakera berean. Lomuto-ren partizio-eskema ezagunago bihurtu zen Introduction to Algorithmsargitaratuta, nahiz eta Hoare-ren eskema baino maila baxuagokoa izan, batez beste hiru aldiz swap gehiago egiten dituelako, eta elementu guztiak berdinak direnean O(n2) denbora-tartetra degradatzen delako.

2009an, Vladimir Yaroslavskiyk pibot bikoitzeko Quicksort berria proposatu zuen. Java core liburutegiko posta zerrendetan, eztabaida bat hasi zuen bere algoritmo berria orduko ordenazio-metodoen gainetik zegoela (garai hartan oso erabilia eta arretaz moldatua zen Bentley eta McIlroy Quicksort klasikoeak ziren). Yaroslavskiy-ren Quicksort hautatu zuten orduan Oracleko Java 7-ko liburutegian ordenatze-algoritmo berri gisa, errendimendu enpirikozko proba asko egin ondoren.

Algoritmoa 

Quicksort zatitu eta irabazi erako algoritmoa da. Sarrerako zenbaki-bektorea bi azpiatal txikiagoetan banatzen du: elementu baxuak batetik eta elementu altuak bestetik. Azpiegitura horiekk ordenatzen ditu modu errekurtsiboan. Quicksort tokian (in-place) jartzeko urratsak hauek dira:

 Aukeratu bektoreko elementu bat pibot deritzona.
 Partizioa: berordenatu bektorea pibota baino balio txikiagoko elementu guztiak pibota baino lehenago gera daitezen, eta pibota baino balio handiagoko elementu guztiak haren atzetik (pibotaren balio berdinak edozein aldetara joan daitezke). Partizioa bukatuta, pibota bere azken posizioan dago. Partizio eragiketa deritzo honi.
 Errekurtsiboki aplikatu goiko urratsak azpibektore bietan.

Errekurtsioko oinarrizko kasuak zero edo bat tamaina duten bektoreak dira, definizioaren arabera berez ordenatuta daudenak, beraz ez dira inoiz ordenatu behar.

Pibota hautatu eta zatitzeko urratsak hainbat modutan egin daitezke; inplementazio-eskema espezifikoak aukeratzeak asko eragiten du algoritmoaren errendimenduan.

Lomuto-ren partizio-eskema 
Eskema hau Nico Lomutori egotzita dago eta Bentleyk bere Programming Pearls eta Cormen et al liburuan ezagun egin du. beren liburuan Introduction to Algorithms. Eskema honek sekuentziaren azken elementua aukeratzen du pibot gisa. Algoritmoak i indizea mantentzen du bektoreko indize moduan, eta jbeste bat (j) erabiltzen du bektoreko elementuak arakatzeko. Eskema hau trinkoagoa eta ulertzeko erraza denez, sarrerako materialetan erabiltzen da maiz, Hoare-ren jatorrizko eskema baino efizienteagoa bada ere. Eskema hau O(n2) mailara degradatzen da bektorea ordenatuta dagoenean. Errendimendua hobetzeko hainbat aldaera proposatu izan dira, besteak beste, pibota hautatzeko hainbat modu, elementu berdinak jorratzeko eta ordenatzeko beste algoritmoak erabiltzea, hala nola txertaketa-ordenazioa bektore txikiekin, eta abar. Ondoko sasikodedean, A bektoreko lo eta hi indizeen arteko elementuak quicksort bidez ordenatzen dituen  algoritmo bat:
 algoritmoa quicksort (A, lo, hi)
   baldin lo < hi orduan
     p := partizioa (A, lo, hi)
     quicksort (A, lo, p - 1)
     quicksort (A, p + 1, hi)
 
 algoritmoa partizioa (A, lo, hi) 
   pibota : = A [hi]
   i : = lo
   j guztietarako hi-tik lo-raino egin
     baldin A[j] < pibota orduan
       trukatu A[i] A[j]-rekin
       i := i + 1
   trukatu A[i] A[hi]-rekin
   itzuli i 
A bektore osoa honela ordenatzen da:  

quicksort (A, 0, length(A) - 1)

Hoare partizioaren eskema 
CAR Hoare-k deskribatutako jatorrizko partizioaren eskemak zatitzaileen muturretan hasten diren bi aurkibide erabiltzen ditu, eta gero elkarrengana mugitzen dira, alderantzizkoa antzematen duten arte: elementu pare bat, biribila baino handiagoa edo berdina, txikiagoa edo berdinak, bata bestearen aldean dauden orden okerrean daudenak. Alderantzikatutako elementuak aldatu egingo dira.  Indizeak elkartzen direnean, algoritmoa azken indizea itzultzen da. Hoare-ren eskema Lomuto partizioaren eskema baino eraginkorragoa da batez beste hiru aldiz gutxiago egiten duelako eta partizio eraginkorrak sortzen ditu balio guztiak berdinak direnean ere. Lomuto-ren partizio eskemaren antzera, Hoare-ren partizioak ere Quicksort-ek O(n2) mailara degradatuko luke dagoeneko ordenatutako sarrerako, pibota lehenengo edo azken elementutzat aukeratu bazen. Erdiko elementua ardatz gisa hartuta, ordea, ordenatu egin ziren datuak (ia) tamaina berdineko partizioetan swapsik gabe, eta horrek Quicksort-ren kasurik onena ekarriko du, hau da. O(n log(n)). Besteak bezala, Hoare-ren banaketak ez du era egonkorrik sortzen. Hala ere, partizioaren algoritmoa bermatuta dago, horrek suposatzen du bi partizioak hutsik ez daudela, beraz ez dago errekurtsio infinitua izateko arriskurik.
 algoritmoa quicksort (A, lo, hi)
   baldin lo < hi orduan
     partizio_muga := partizioa (A, lo, hi)
     quicksort (A, lo, partizio_muga)
     quicksort (A, partizio_muga + 1, hi)
 
 algoritmoa partizioa (A, lo, hi)
   pibota := A [⌊(hi + lo) / 2⌋]
   i : = lo
   j : = hi
   begizta betirako
     while A[i] < pibota
       i := i + 1
     while A[j] > pibota
       j := j - 1
     baldin ≥ j orduan
       itzuli j
     trukatu A[i] A[j]-rekin
     i := i + 1
     j := j - 1 
Pibot elementua aukeratzeko puntu garrantzitsua da zatiketaren emaitza zerorantz borobiltzea. Hori da programazio lengoaietako zenbait zatiketaren portaera inplizitua (adibidez, C, C ++, Java), hortaz, borobiltzea ezarrita dago kode inplementatzean. Hemen solairuko funtzio esplizituaz azpimarratzen da, eta  sinbolo bikotearekin adierazten da. Borobiltzea garrantzitsua da A [hi] pibot gisa erabiltzea saihesteko, eta horrek errekurtsio infinitua sor dezake.

A bektore osoa honela ordenatzen da: quicksort (A, 0, length(A) - 1)

Erreferentziak

Kanpo estekak 
 opendatastructures.org - 11.1.2 atala - Quicksort, Pat Morin
 Quicksort-en ilustrazio interaktiboa, kode aurrerapenarekin

Ordenatzea
Algoritmoak