Zatitu eta irabazi erako algoritmo

Informatikan, Zatitu eta irabazi erako algoritmoak estrategi hau erabiltzen dituzten algoritmoak dira:

• 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.

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

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 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 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.

Kanpo estekak

• Datuak: Q671298
• Multimedia: Divide-and-conquer algorithms / Q671298