Quicksort

[thumb|Hoarek [Quicksort ordenazio-algoritmoa asmatu zuen. Lerro urdina pibot balioa da.]]
**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(*n*2) 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. Lomuto-ren partizio-eskema ezagunago bihurtu zen *Introduction to Algorithms*argitaratuta, 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 
eskuinera|thumb|400x400px| Quicksort-en adibide osoa ausazko zenbaki multzo batean aplikatuta.
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 2) 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  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