Zatitu eta irabazi erako algoritmo

Wikipedia, Entziklopedia askea
Array baten balio maximoa bilatzea 'zatitu eta irabazi' algoritmoaren arabera. Koloreak: (urdina) - (azpi)tartea, (gorria) - (azpi)arrayko maximoa, (horia) - subarray-aren prozesatze-ordena

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.

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[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.[4]

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[aldatu | aldatu iturburu kodea]

  1. Santos, Rosa Arruabarrena. (1997). Algoritmika. UEU arg ISBN 978-84-86967-81-9 . Noiz kontsultatua: 2020-06-07.
  2. «Sir Antony Hoare | Computer History Museum» web.archive.org 2015-04-03 . Noiz kontsultatua: 2020-06-07.
  3. Hoare, C. A. R.. (1961-07-01). «Algorithm 64: Quicksort» Communications of the ACM (7): 321 doi:10.1145/366622.366644 . Noiz kontsultatua: 2020-06-07.
  4. Santos, Rosa Arruabarrena. (1997). Algoritmika. UEU arg ISBN 978-84-86967-81-9 . Noiz kontsultatua: 2020-06-07.

Kanpo estekak[aldatu | aldatu iturburu kodea]