Zatitu eta irabazi erako algoritmo
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.
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