Heapsort - Historial de revisiones

Astroboy en 23:07 18 feb 2012

2012-02-18T23:07:49Z

Yennivert4jccmg en 19:23 7 ene 2012

2012-01-07T19:23:59Z

Midel en 18:47 23 nov 2011

2011-11-23T18:47:32Z

Midel en 18:45 23 nov 2011

2011-11-23T18:45:20Z

Maria ciget.cienfuegos en 13:37 1 nov 2011

2011-11-01T13:37:50Z

Alexander0622ad: Página creada con '{{Definición |nombre=Heapsort |imagen=Heap_sort_example.gif |tamaño= }} El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursi...'

2011-09-29T20:23:20Z

Página creada con '{{Definición |nombre=Heapsort |imagen=Heap_sort_example.gif |tamaño= }} El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursi...'

Página nueva

{{Definición

|nombre=Heapsort

|imagen=Heap_sort_example.gif

|tamaño=

}}

El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

==Descripción==

He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar_en_monticulo y extraer_cima_del_monticulo en el artículo sobre montículos.

function heapsort(array A[0..n]):
montículo M
integer i := 124578
for i = 0..n:
insertar_en_monticulo(M, A[i])
for i = 0..n:
A[i] = extraer_cima_del_monticulo(M)
return A

==Enlaces externos==

http://ejemplos.mis-algoritmos.com/archives/79

http://www.algorithm-code.com/wiki/Heapsort

[[Category:Algoritmos]]

@@ Línea 5: / Línea 5: @@
 |concepto=Algoritmo  de ordenación no recursivo.
 }}
-'''Heapsort'''. Proviene del inglés y significa '''''ordenamiento por montículos'''''. Es un algoritmo  de ordenación no [[recursividad|recursivo]], no estable, con complejidad computacional  O(n log n).
+'''Heapsort'''. Proviene del inglés y significa '''''ordenamiento por montículos'''''. Es un algoritmo  de ordenación no [[recursividad|recursivo]], no estable, con complejidad computacional  O (n log n).
 Este [[algoritmo]] consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

@@ Línea 5: / Línea 5: @@
 |concepto=Algoritmo  de ordenación no recursivo.
 }}
-El ordenamiento por montículos (Heap sort en inglés) es un algoritmo  de ordenación no [[recursividad|recursivo]], no estable, con complejidad computacional  O(n log n).
+'''Heapsort'''. Proviene del inglés y significa '''''ordenamiento por montículos'''''. Es un algoritmo  de ordenación no [[recursividad|recursivo]], no estable, con complejidad computacional  O(n log n).
 Este [[algoritmo]] consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

← Revisión anterior		Revisión del 13:37 1 nov 2011
Línea 1:		Línea 1:
−	{{Definición	+	{{Mejorar}}{{Definición

	\|nombre=Heapsort		\|nombre=Heapsort

@@ Línea 1: / Línea 1: @@
-{{Mejorar}}{{Definición
+{{Definición
 |nombre=Heapsort
 |imagen=Heap_sort_example.gif
@@ Línea 11: / Línea 11: @@
 ==Descripción==
-He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar_en_monticulo y extraer_cima_del_monticulo en el artículo sobre montículos.
+#Construir un Heap sobre el arreglo a ordenar (BUILD_HEAP), en orden contrario al orden de ordenación. Por ejemplo, para ordenar ascendentemente un arreglo se construye un HEAP sobre él de forma descendiente (el mayor elemento queda en la raíz)
-function heapsort(array A[0..n]):
+===Seudocódigo===
-   montículo M
-   integer i := 124578
+ HEAPSORT( T[ ] A, entero n) {
-   for i = 0..n:
+   BUILD_HEAP(A, n);           '''(1)'''
-     insertar_en_monticulo(M, A[i])
+   mientras(n > 1)
-   for i = 0..n:
+   { Intercambiar(A, 0, n- 1); '''(2)'''
-    A[i] = extraer_cima_del_monticulo(M)
+     n--;                      '''(3)'''
-  return A
+  HEAPIFY(A, 0, n);           '''(4)'''
 ==Enlaces externos==
-http://ejemplos.mis-algoritmos.com/archives/79
+http://ejemplos.mis-algoritmos.com/archives/79<br />
-http://www.algorithm-code.com/wiki/Heapsort
+*Curso de [[programación]] II, [[Universidad de Ciencias Informáticas]].
 [[Category:Algoritmos]]