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^[1] eta 1961ean argitaratu zuen,^[2] ohiko ordenatze-algoritmo bat da oraindik. Ongi inplementatzen denean, beste algoritmo lehiakide nagusiak (merge-sort eta heapsort) baino bizpahiru aldiz azkarragoa izan daiteke.^[3]

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²) alderaketak egiten ditu, nahiz eta kasu hori arraroa izan.^[4]

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.^[5] 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.^[2]^[6]

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,^[7] 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)^[8] analisiarekin lotutako arazo ireki asko konpondu zituen, baita espero diren konparaketa eta swap kopurua ere.^[7] 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.^[9] 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.^[10]

2009an, Vladimir Yaroslavskiyk pibot bikoitzeko Quicksort berria proposatu zuen.^[11] 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,^[12] errendimendu enpirikozko proba asko egin ondoren.^[13]

Algoritmoa

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.^[14]^[15] 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.^[16] 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. ^[17] 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.^[16] Lomuto-ren partizio eskemaren antzera, Hoare-ren partizioak ere Quicksort-ek O(n²) 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

↑ «Sir Antony Hoare | Computer History Museum» web.archive.org 2015-04-03 (Noiz kontsultatua: 2020-06-07).
↑ ^a ^b Hoare, C. A. R.. (1961-07-01). «Algorithm 64: Quicksort» Communications of the ACM 4 (7): 321. doi:10.1145/366622.366644. (Noiz kontsultatua: 2020-06-07).
↑ Santos, Rosa Arruabarrena. (1997). Algoritmika. UEU arg ISBN 978-84-86967-81-9. (Noiz kontsultatua: 2020-06-07).
↑ Skiena, Steven S.. (2008). The algorithm design manual. (2nd ed. argitaraldia) Springer ISBN 978-1-84800-070-4. PMC 370729337. (Noiz kontsultatua: 2020-06-07).
↑ (Ingelesez) Shustek, Len; Hoare, C.A.R.. (2009-03). «InterviewAn interview with C.A.R. Hoare» Communications of the ACM 52 (3): 38–41. doi:10.1145/1467247.1467261. ISSN 0001-0782. (Noiz kontsultatua: 2020-06-07).
↑ «My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort» My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort (Noiz kontsultatua: 2020-06-07).
↑ ^a ^b (Ingelesez) Bentley, Jon L.; McIlroy, M. Douglas. (1993-11). «Engineering a sort function» Software: Practice and Experience 23 (11): 1249–1265. doi:10.1002/spe.4380231105. (Noiz kontsultatua: 2020-06-07).
↑ van Emden, M. H.. (1970-11-01). «Algorithms 402: Increasing the efficiency of quicksort» Communications of the ACM 13 (11): 693–694. doi:10.1145/362790.362803. (Noiz kontsultatua: 2020-06-07).
↑ Beautiful code. O'Reilly 2007 ISBN 978-0-596-51004-6. PMC 163289538. (Noiz kontsultatua: 2020-06-07).
↑ «algorithms - Quicksort Partitioning: Hoare vs. Lomuto» Computer Science Stack Exchange (Noiz kontsultatua: 2020-06-07).
↑ «Wayback Machine» web.archive.org 2015-10-02 (Noiz kontsultatua: 2020-06-07).
↑ «Arrays (Java Platform SE 7 )» docs.oracle.com (Noiz kontsultatua: 2020-06-07).
↑ (Ingelesez) Wild, Sebastian; Nebel, Markus; Reitzig, Raphael; Laube, Ulrich. (2013-01-07). Sanders, Peter ed. «Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn» 2013 Proceedings of the Fifteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Society for Industrial and Applied Mathematics): 55–69. doi:10.1137/1.9781611972931.5.. ISBN 978-1-61197-253-5. (Noiz kontsultatua: 2020-06-07).
↑ Bentley, Jon. (1985-06-01). «Programming pearls» Communications of the ACM 28 (6): 570–576. doi:10.1145/3812.315108. ISSN 0001-0782. (Noiz kontsultatua: 2020-06-07).
↑ Introduction to algorithms. (Third edition. argitaraldia) MIT Press 2009 ISBN 978-0-262-27083-0. PMC 676697295. (Noiz kontsultatua: 2020-06-07).
↑ ^a ^b «algorithms - Quicksort Partitioning: Hoare vs. Lomuto» Computer Science Stack Exchange (Noiz kontsultatua: 2020-06-07).
↑ (Ingelesez) Hoare, C. A. R.. (1962-01-01). «Quicksort» The Computer Journal 5 (1): 10–16. doi:10.1093/comjnl/5.1.10. ISSN 0010-4620. (Noiz kontsultatua: 2020-06-07).

Kanpo estekak

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

Datuak: Q486598
Multimedia: Quicksort / Q486598

[1] «Sir Antony Hoare | Computer History Museum» web.archive.org 2015-04-03 (Noiz kontsultatua: 2020-06-07).

[:0-2] Hoare, C. A. R.. (1961-07-01). «Algorithm 64: Quicksort» Communications of the ACM 4 (7): 321. doi:10.1145/366622.366644. (Noiz kontsultatua: 2020-06-07).

[3] Santos, Rosa Arruabarrena. (1997). Algoritmika. UEU arg ISBN 978-84-86967-81-9. (Noiz kontsultatua: 2020-06-07).

[4] Skiena, Steven S.. (2008). The algorithm design manual. (2nd ed. argitaraldia) Springer ISBN 978-1-84800-070-4. PMC 370729337. (Noiz kontsultatua: 2020-06-07).

[5] (Ingelesez) Shustek, Len; Hoare, C.A.R.. (2009-03). «InterviewAn interview with C.A.R. Hoare» Communications of the ACM 52 (3): 38–41. doi:10.1145/1467247.1467261. ISSN 0001-0782. (Noiz kontsultatua: 2020-06-07).

[6] «My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort» My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort (Noiz kontsultatua: 2020-06-07).

[:1-7] (Ingelesez) Bentley, Jon L.; McIlroy, M. Douglas. (1993-11). «Engineering a sort function» Software: Practice and Experience 23 (11): 1249–1265. doi:10.1002/spe.4380231105. (Noiz kontsultatua: 2020-06-07).

[8] van Emden, M. H.. (1970-11-01). «Algorithms 402: Increasing the efficiency of quicksort» Communications of the ACM 13 (11): 693–694. doi:10.1145/362790.362803. (Noiz kontsultatua: 2020-06-07).

[9] Beautiful code. O'Reilly 2007 ISBN 978-0-596-51004-6. PMC 163289538. (Noiz kontsultatua: 2020-06-07).

[10] «algorithms - Quicksort Partitioning: Hoare vs. Lomuto» Computer Science Stack Exchange (Noiz kontsultatua: 2020-06-07).

[11] «Wayback Machine» web.archive.org 2015-10-02 (Noiz kontsultatua: 2020-06-07).

[12] «Arrays (Java Platform SE 7 )» docs.oracle.com (Noiz kontsultatua: 2020-06-07).

[13] (Ingelesez) Wild, Sebastian; Nebel, Markus; Reitzig, Raphael; Laube, Ulrich. (2013-01-07). Sanders, Peter ed. «Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn» 2013 Proceedings of the Fifteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Society for Industrial and Applied Mathematics): 55–69. doi:10.1137/1.9781611972931.5.. ISBN 978-1-61197-253-5. (Noiz kontsultatua: 2020-06-07).

[14] Bentley, Jon. (1985-06-01). «Programming pearls» Communications of the ACM 28 (6): 570–576. doi:10.1145/3812.315108. ISSN 0001-0782. (Noiz kontsultatua: 2020-06-07).

[15] Introduction to algorithms. (Third edition. argitaraldia) MIT Press 2009 ISBN 978-0-262-27083-0. PMC 676697295. (Noiz kontsultatua: 2020-06-07).

[:2-16] «algorithms - Quicksort Partitioning: Hoare vs. Lomuto» Computer Science Stack Exchange (Noiz kontsultatua: 2020-06-07).

[17] (Ingelesez) Hoare, C. A. R.. (1962-01-01). «Quicksort» The Computer Journal 5 (1): 10–16. doi:10.1093/comjnl/5.1.10. ISSN 0010-4620. (Noiz kontsultatua: 2020-06-07).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]