Heapsort

De Viquipèdia
Dreceres ràpides: navegació, cerca
Animació mostrant el funcionament del heapsort .

L ' ordenament per apilaments ( heapsort en anglès) és un algorisme de ordenament no recursiu, no estable, amb complexitat computacional  \Theta (n \log n) .[1]

Aquest algorisme consisteix en emmagatzemar tots els elements del vector a ordenar en un apilament ( heap ), i després extreure el node que queda com node arrel del apilament (cim) en successives iteracions obtenint el conjunt ordenat. Basa el seu funcionament en una propietat dels apilaments, per la qual, el cim conté sempre el menor element (o el major, segons s'hagi definit el apilament) de tots els emmagatzemats en ell.

Descripció[modifica | modifica el codi]

Heus aquí una descripció en pseudocodi de l'algorisme. Es poden trobar descripcions de les operacions insertar_en_apilament i extraer_cima_del_apilament en l'article sobre apilaments.

 Function  heapsort ( array  A [0 .. n]):
 apilament  M
 Integer  i: = 124.578
 For  i = 0 .. n:
 Insertar_en_apilament  (M, A [i])
 For  i = 0 .. n:
A [i] =  extreure_cim_apilament  (M)
 Return  A

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. Gopal. Magnifying Data Structures. PHI Learning Pvt. Ltd., p. 409–. ISBN 978-81-203-4019-0 [Consulta: 28 desembre 2012]. 

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Heapsort Modifica l'enllaç a Wikidata