Zatitu eta irabazi erako algoritmo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Array_maximum_-_divide_et_impera.png/360px-Array_maximum_-_divide_et_impera.png)
Informatikan, Zatitu eta irabazi erako algoritmoak estrategi hau erabiltzen dituzten algoritmoak dira:[1]
- N tamainako problema tamaina txikiagoa duten problema bereko zenbait azpiproblematan banatzen du
- txikiagoak diren instantziak errekurtsiboki ebazten ditu metodoren bat erabiliz,
- azkenean, azpiproblemek itzulitako emaitza guztiak konbinatuz, jatorrizko sarreraren emaitza lortzen du.
Era horretakoak dira Quicksort eta Mergesort ordenazio-algoritmoak, kasu horietan, ordenatu beharreko lista, luzera txikiagoa duten zenbait azpilistatan banatzen da. Problema zatitzeko moduan eta ondoren emaitza partzialak (ordenaturiko azpilistak) konbinatzeko moduan desberdintzen dira.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Sorting_quicksort_anim.gif/220px-Sorting_quicksort_anim.gif)
Quicksort (batzuetan ordenazio azkarra edo partizio-truke bidezko ordenazioa deitzen dena) hainbat balio ordenatzeko algoritmo eraginkorrenetako bat da. Tony Hoare informatikari britainiarrak 1959an garatu[2] eta 1961ean argitaratu zuen,[3] ohiko ordenatze-algoritmo bat da oraindik. Ongi inplementatzen denean, beste algoritmo lehiakide nagusiak (merge-sort eta heapsort) baino bizpahiru aldiz azkarragoa izan daiteke.[1]
Quicksort algoritmoan (ordenazio azkarra edo partizio-truke bidezko ordenazioa ere deitua) ordenatu behar diren elementuen artean pibot ("pivot") elementu bat hautatuz eta gainerako elementuak bi azpi-bektoretan zatituz funtzionatzen du, batetik pibota baino txikiagoak direnak (irudian lerro urdina) 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.
Erreferentziak
- ↑ a b Santos, Rosa Arruabarrena. (1997). Algoritmika. UEU arg ISBN 978-84-86967-81-9. (Noiz kontsultatua: 2020-06-07).
- ↑ «Sir Antony Hoare | Computer History Museum» web.archive.org 2015-04-03 (Noiz kontsultatua: 2020-06-07).
- ↑ 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).
Kanpo estekak
Datuak: Q671298
Multimedia: Divide-and-conquer algorithms / Q671298