1. No category

Algoritmos y Estructura de Datos Parte 4 de 7: Búsqueda y Clasificación Libros de Wikipedia 2015 Por Wikipedians EDITADO POR: Reiner Creutzburg, Montserrat Rodríguez, Dulce García, María Martínez Fachhochschule Brandenburg Fachbereich Informatik und Medien PF 2132 D-­‐14737 Brandenburg , Germany Email: creutzburg@fh-­‐brandenburg.de Índice general
1
2
Busqueda
1
1.1
Algoritmo de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Búsqueda secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Búsqueda dicotómica (binaria) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.3
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Clasificacion
3
2.1
Algoritmo de agrupamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.3
Véase también . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.4
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.5
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.1
Descripción del algoritmo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.2
Ejemplo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.3
Véase también . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.4
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Ordenamiento por mezcla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3.1
Descripción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3.2
Optimizando merge sort
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3.3
Comparación con otros algoritmos de ordenamiento . . . . . . . . . . . . . . . . . . . . .
6
2.3.4
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Ordenamiento por inserción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4.1
Véase también . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4.2
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.5.1
Descripción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.5.2
Enlaces externos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
2.3
2.4
2.5
3
Text and image sources, contributors, and licenses
9
3.1
Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.2
Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
i
Algoritmos y Estructura de Datos Parte 4: Búsqueda y Clasificación Libros de Wikipedia 2015 Por Wikipedians EDITADO POR: Reiner Creutzburg, Montserrat Rodríguez, Dulce García, María Martínez . Fachhochschule Brandenburg Fachbereich Informatik und Medien PF 2132 D-­‐14737 Brandenburg Email: creutzburg@fh-­‐brandenburg.de Capítulo 1
Busqueda
1.1 Algoritmo de búsqueda
1.1.2 Búsqueda dicotómica (binaria)
Se utiliza cuando el vector en el que queremos determinar
la existencia de un elemento está previamente ordenado.
Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número
de iteraciones necesarias.
Un algoritmo de búsqueda es aquel que está diseñado
para localizar un elemento con ciertas propiedades dentro
de una estructura de datos; por ejemplo, ubicar el registro
correspondiente a cierta persona en una base de datos, o
el mejor movimiento en una partida de ajedrez.
Está altamente recomendado para buscar en arrays
La variante más simple del problema es la búsqueda de
de gran tamaño. Por ejemplo, en uno conteniendo
un número en un vector.
50.000.000 elementos, realiza como máximo 26 compaBúsqueda dicotómica
raciones (en el peor de los casos).
Elementos necesarios en una búsqueda :
Para implementar este algoritmo se compara el elemento
a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor
que el del elemento buscado se repite el procedimiento
en la parte del array que va desde el inicio de éste hasta
el elemento tomado, en caso contrario se toma la parte
del array que va desde el elemento tomado hasta el final.
De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si
el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra
en todo el array.
log2 (n) donde n = elementos de la búsqueda
Ejemplo: log2 (1.000.000) ≈ 20
1.1.1
Búsqueda secuencial
Se utiliza cuando el vector no está ordenado o no puede
ser ordenado previamente. Consiste en buscar el elemento
comparándolo secuencialmente (de ahí su nombre) con
cada elemento del vector hasta encontrarlo, o hasta que se
llegue al final. La existencia se puede asegurar cuando el
elemento es localizado, pero no podemos asegurar la no
existencia hasta no haber analizado todos los elementos
del vector. A continuación se muestra el pseudocódigo
del algoritmo:[cita requerida]
A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central
del array.
Datos de entrada: vec: vector en el que se desea buscar
el dato tam: tamaño del vector. Los subíndices válidos
van desde 0 hasta tam-1 inclusive. dato: elemento que se
quiere buscar. Variables centro: subíndice central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo inf = 0 sup = tam-1 Mientras inf <= sup:
centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción Si vec[centro] == dato devolver verdadero
y/o pos, de lo contrario: Si dato < vec[centro] entonces:
sup = centro - 1 En caso contrario: inf = centro + 1 Fin
(Mientras) Devolver Falso
Datos de entrada: vec: vector en el que se desea buscar
el dato tam: tamaño del vector. Los subíndices válidos
van desde 0 hasta tam-1 inclusive. Puede representarse
así: vec[0...tam) ó vec[0...tam-1]. dato: elemento que se
quiere buscar. Variables pos: posición actual en el vector pos = 0 while pos < tam: if vec[pos] == dato: Retorne
verdadero y/o pos, else: pos = pos + 1 Fin (while) Retorne
falso,
• C
• C
int busquedaSimple(int vector[n], int n, int dato) { int i;
for(i=0; i<n; i++){ if(dato==vector[i]) { return i; break; int busquedaBinaria(int vector[], int n, int dato)
} } return −1; }
{ int centro,inf=0,sup=n-1; while(inf<=sup){ centro=(sup+inf)/2; if(vector[centro]==dato) return centro;
1
2
CAPÍTULO 1. BUSQUEDA
else if(dato < vector[centro]) sup=centro-1; else 1.1.3 Enlaces externos
inf=centro+1; } return −1; }
• ALT: Algorithm Learning Tool. Herramienta de
apoyo a la enseñanza de algoritmos que muestra gráImplementación recursiva en C++ [cita requerida]
ficamente su funcionamiento. Permite implementar
algoritmos propios y realizar una ejecución dinámi• C++
ca e interactiva
#include <iostream> #include <vector> bool busqueda_dicotomica(const vector<int> &v, int principio,
int fin, int &x){ bool res; if(principio <= fin){ int
m = (principio + fin)/2; if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x); else if(x > v[m]) res
= busqueda_dicotomica(v, m+1, fin, x); else res = true;
}else res = false; return res; } /*{Post: Si se encuentra
devuelve true, sino false}*/
Implementación recursiva en Python
• Python
def busquedaBinaria (numeros, inicio, fin, elemento):
if (inicio == fin): return numeros [inicio] == elemento
centro = (inicio + fin) // 2 if (elemento < numeros [centro]): return busquedaBinaria (numeros, inicio, centro,
elemento) elif (elemento > numeros [centro]): return
busquedaBinaria (numeros, centro + 1, fin, elemento)
else: return True def busqueda (numeros, elemento): if
(numeros == None) or (numeros == []): return False
else: return busquedaBinaria (numeros, 0, len (numeros)
- 1, elemento)
Implementación recursiva en Python3
• Python
def bin(a,x,low,hi): ans = −1 if low==hi: ans = −1
else: mid = (low+((hi-low)//2)) if x < a[mid]: ans =
bin(a,x,low,mid) elif x > a[mid]: ans = bin(a,x,mid+1,hi)
else: ans = mid return ans # Así se hace el llamado:
print(binseacrh(Lista,a_buscar,0,len(Lista))) # Retorna
el indice que coincide con 'numero a buscar', sino está
retorna −1 # Tiempo: (log n)
Implementación iterativa en Python3
• Python
def bin(a, c): ans = −1 if a[0] >= c: ans = −1 else:
low, hi = 0, len(a) while low+1 != hi: mid = low +
((hi-low)//2) if a[mid] < c: low = mid else: hi = mid ans =
low return ans # Así se hace el llamado: print(bin(lista(),
numero_a_buscar) ) # Retorna el indice que coincide
con 'numero a buscar', sino está retorna −1 # Tiempo:
(log n)
Capítulo 2
Clasificacion
2.1 Algoritmo de agrupamiento
2.1.2 Algoritmos
Un algoritmo de agrupamiento (en inglés, clusteri- Existen dos grandes técnicas para el agrupamiento de cang) es un procedimiento de agrupación de una serie de sos:
vectores de acuerdo con un criterio. Esos criterios son
por lo general distancia o similitud. La cercanía se defi• Agrupamiento jerárquico, que puede ser aglomerane en términos de una determinada función de distancia,
tivo o divisivo.
como la euclídea, aunque existen otras más robustas o
• Agrupamiento no jerárquico, en los que el númeque permiten extenderla a variables discretas. La mediro de grupos se determina de antemano y las obserda más utilizada para medir la similitud entre los casos
vaciones se van asignando a los grupos en función
es las matriz de correlación entre los nxn casos. Sin emde su cercanía. Existen los métodos de k-mean y kbargo, también existen muchos algoritmos que se basan
medioid.
en la máximización de una propiedad estadística llamada
verosimilitud.
Generalmente, los vectores de un mismo grupo (o clús- Existen diversas implementaciones de algoritmos concreters) comparten propiedades comunes. El conocimiento tos. Por ejemplo, el de las k-medias, de particionamiento.
de los grupos puede permitir una descripción sintética de Es uno de los más antiguos pero uso extendido a pesar de
un conjunto de datos multidimensional complejo. De ahí sus carencias y falta de robustez.
su uso en minería de datos. Esta descripción sintética se El paquete clúster de R-lenguaje [1] implementa una serie
consigue sustituyendo la descripción de todos los elemen- de algoritmos de particionamiento como agnes, mona y
tos de un grupo por la de un representante característico diana, jerárquicos, y pam, clara y fanny, de particionadel mismo.
miento.
En algunos contextos, como el de la minería de datos,
se lo considera una técnica de aprendizaje no supervisado puesto que busca encontrar relaciones entre variables 2.1.3 Véase también
descriptivas pero no la que guardan con respecto a una
• Inteligencia de enjambre
variable objetivo.
2.1.1
2.1.4 Referencias
Aplicaciones
[1] Rousseeuw, P.J.; Kaufman, L. (1990). Finding Groups in
Data: An Introduction to Clúster Analysis. Wiley.
Las técnicas de agrupamiento encuentran aplicación en
diversos ámbitos.
• En biología para clasificar animales y plantas.
2.1.5 Enlaces externos
• En medicina para identificar enfermedades.
•
• En marketing para identificar personas con hábitos
de compras similares.
• En teoría de la señal pueden servir para eliminar ruidos.
Wikimedia Commons alberga contenido
multimedia sobre Algoritmo de agrupamientoCommons.
• Implementación Real en C del algoritmo EM para
Clustering con Gaussian Mixture Models (GMMs).
• En biometría para identificación del locutor o de caras.
• Recuperación de Información
3
4
CAPÍTULO 2. CLASIFICACION
2.2 Quicksort
• En el peor caso, el pivote termina en un extremo de
la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente
ocurre en listas que se encuentran ordenadas, o casi
ordenadas. Pero principalmente depende del pivote,
si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y
el array que le pasamos está ordenado, siempre va
a generar a su izquierda un array vacío, lo que es
ineficiente.
• En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de optimizaciones
que se aplican al algoritmo se centren en la elección del
pivote.
Quicksort en acción sobre una lista de números aleatorios. Las
líneas horizontales son valores pivote.
El ordenamiento rápido (quicksort en inglés) es un
algoritmo creado por el científico británico en computación C. A. R. Hoare, basado en la técnica de divide y
vencerás, que permite, en promedio, ordenar n elementos
en un tiempo proporcional a n log n.
Demostración de un caso particular
Supongamos que el número de elementos a ordenar es una
potencia de dos, es decir, n = 2k para algún natural k .
Inmediatamente k = log2 (n) , donde k es el número de
divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrá n comparaciones.
En la segunda fase el algoritmo instanciará dos sublis2.2.1 Descripción del algoritmo
tas de tamaño aproximadamente n/2. El número total de
comparaciones de estas dos sublistas es: 2(n/2) = n. En
El algoritmo trabaja de la siguiente forma:
la tercera fase el algoritmo procesará 4 sublistas más, por
tanto el número total de comparaciones en esta fase es
• Elegir un elemento de la lista de elementos a orde- 4(n/4) = n.
nar, al que llamaremos pivote.
En conclusión, el número total de comparaciones que ha• Resituar los demás elementos de la lista a cada lado ce el algoritmo es:
del pivote, de manera que a un lado queden todos los n + n + n + ..... + n = kn , donde k = log (n) , por
2
menores que él, y al otro los mayores. Los elemen- tanto el Orden de Complejidad del algoritmo en el peor
tos iguales al pivote pueden ser colocados tanto a su caso es O(n.log n) .
2
derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote
ocupa exactamente el lugar que le corresponderá en Técnicas de elección del pivote
la lista ordenada.
El algoritmo básico del método Quicksort consiste en to• La lista queda separada en dos sublistas, una forma- mar cualquier elemento de la lista al cual denominaremos
da por los elementos a la izquierda del pivote, y otra como pivote, dependiendo de la partición en que se elija,
por los elementos a su derecha.
el algoritmo será más o menos eficiente.
• Repetir este proceso de forma recursiva para cada
sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
• Tomar un elemento cualquiera como pivote tiene la
ventaja de no requerir ningún cálculo adicional, lo
cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo
tenga un orden de O(n²) para ciertas permutaciones
de los elementos en la lista.
• En el mejor caso, el pivote termina en el centro de la
lista, dividiéndola en dos sublistas de igual tamaño.
En este caso, el orden de complejidad del algoritmo
es O(n·log n).
• Otra opción puede ser recorrer la lista para saber de
antemano qué elemento ocupará la posición central
de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los
casos, el algoritmo sea O(n·log n). No obstante, el
2.2. QUICKSORT
cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.
• La opción a medio camino es tomar tres elementos
de la lista - por ejemplo, el primero, el segundo, y el
último - y compararlos, eligiendo el valor del medio
como pivote.
5
• Pese a que en secuencias largas de elementos la probabilidad de hallarse con una configuración de elementos “crítica” es muy baja, esto no evita que sigan apareciendo (a veces, de manera intencionada).
El algoritmo introsort es una extensión del algoritmo quicksort que resuelve este problema utilizando
heapsort en vez de quicksort cuando el número de
recursiones excede al esperado.
Técnicas de reposicionamiento
Nota: Los tres parámetros de la llamada inicial a Quicksort serán array[0], 0, numero_elementos −1, es decir, si
Una idea preliminar para ubicar el pivote en su posición es un array de 6 elementos array, 0, 5
final sería contar la cantidad de elementos menores que
él, y colocarlo un lugar más arriba, moviendo luego todos
esos elementos menores que él a su izquierda, para que 2.2.2 Ejemplo
pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho más efec- En el siguiente ejemplo se marcan el pivote y los índices
tivo. Se utilizan dos índices: i, al que llamaremos índice i y j con las letras p, i y j respectivamente.
izquierdo, y j, al que llamaremos índice derecho. El al- Comenzamos con la lista completa. El elemento pivote
goritmo es el siguiente:
será el 4:
5-3-7-6-2-1-4p
• Recorrer la lista simultáneamente con i y j: por la
izquierda con i (desde el primer elemento), y por la
derecha con j (desde el último elemento).
Comparamos con el 5 por la izquierda y el 1 por la derecha.
5-3-7-6-2-1-4ijp
• Cuando lista[i] sea mayor que el pivote y lista[j] sea 5 es mayor que 4 y 1 es menor. Intercambiamos:
menor, se intercambian los elementos en esas posi1-3-7-6-2-5-4ijp
ciones.
Avanzamos por la izquierda y la derecha:
• Repetir esto hasta que se crucen los índices.
1-3-7-6-2-5-4ijp
• El punto en que se cruzan los índices es la posición 3 es menor que 4: avanzamos por la izquierda. 2 es menor
adecuada para colocar el pivote, porque sabemos que 4: nos mantenemos ahí.
que a un lado los elementos son todos menores y
al otro son todos mayores (o habrían sido intercam- 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p
biados).
7 es mayor que 4 y 2 es menor: intercambiamos.
1-3-2-6-7-5-4ijp
Transición a otro algoritmo
Como se mencionó anteriormente, el algoritmo quicksort
ofrece un orden de ejecución O(n²) para ciertas permutaciones “críticas” de los elementos de la lista, que siempre
surgen cuando se elige el pivote «a ciegas». La permutación concreta depende del pivote elegido, pero suele corresponder a secuencias ordenadas. Se tiene que la probabilidad de encontrarse con una de estas secuencias es
inversamente proporcional a su tamaño.
Avanzamos por ambos lados:
1 - 3 - 2 - 6 - 7 - 5 - 4 iyj p
En este momento termina el ciclo principal, porque los
índices se cruzaron. Ahora intercambiamos lista[i] con
lista[sup] (pasos 16-18):
1-3-2-4-7-5-6p
Aplicamos recursivamente a la sublista de la izquierda
(índices 0 - 2). Tenemos lo siguiente:
1-3-2
• Los últimos pases de quicksort son numerosos y ordenan cantidades pequeña de elementos. Un porcentaje medianamente alto de ellos estarán dispuestos
de una manera similar al peor caso del algoritmo,
volviendo a éste ineficiente. Una solución a este problema consiste en ordenar las secuencias pequeñas
usando otro algoritmo. Habitualmente se aplica el
algoritmo de inserción para secuencias de tamaño
menores de 8-15 elementos.
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron
los índices termina el ciclo. Se intercambia lista[i] con
lista[sup]:
1-2-3
El mismo procedimiento se aplicará a la otra sublista. Al
finalizar y unir todas las sublistas queda la lista inicial ordenada en forma ascendente.
6
CAPÍTULO 2. CLASIFICACION
1-2-3-4-5-6-7
1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2.2.3
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que
a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que
están ordenadas.
Véase también
• Algoritmo de ordenamiento
2.2.4
Enlaces externos
A continuación se describe el algoritmo en pseudocódigo
• Distintas implementaciones del algoritmo en Wiki(se advierte de que no se incluyen casos especiales para
books (inglés)
vectores vacíos, etc.; una implementación en un lenguaje
• Distintas implementaciones del algoritmo en Roset- de programación real debería tener en cuenta estos detalles):
taCode.org (inglés)
function mergesort(m) var list left, right, result if
length(m) ≤ 1 return m else var middle = length(m) / 2 for
each x in m up to middle - 1 add x to left for each x in m at
2.3 Ordenamiento por mezcla
and after middle add x to right left = mergesort(left) right
El algoritmo de ordenamiento por mezcla (merge sort en = mergesort(right) if last(left) ≤ first(right) append right
inglés) es un algoritmo de ordenamiento externo estable to left return left result = merge(left, right) return result
basado en la técnica divide y vencerás. Es de complejidad function merge(left,right) var list result while length(left)
> 0 and length(right) > 0 if first(left) ≤ first(right) append
O(n log n).
first(left) to result left = rest(left) else append first(right)
to result right = rest(right) if length(left) > 0 append
rest(left) to result if length(right) > 0 append rest(right)
to result return result
2.3.2 Optimizando merge sort
En los ordenadores modernos, el principio de localidad
puede ser primordial en la optimización de software, porque se usan jerarquías de memoria multi-nivel. Se han
propuesto versiones de cache-consciente del algoritmo de
ordenación por mezcla, cuyas operaciones han sido espeEjemplo de ordenamiento por mezcla.
cíficamente escogidas para minimizar el movimiento de
entrada y salida de páginas de la memoria caché de la máquina. Por ejemplo, el algorimo “tiled merge sort” deja de
particionar subarrays cuando se han alcanzado subarrays
2.3.1 Descripción
de tamaño S, donde S es el número de elementos que caFue desarrollado en 1945 por John Von Neumann ben en una única página en memoria. Cada uno de esos
subarrays se ordenan con un algorimo de ordenación in.[cita requerida]
situ, para evitar intercambios en memoria, y entonces se
Conceptualmente, el ordenamiento por mezcla funciona termina con el algoritmo de ordenamiento por mezcla en
de la siguiente manera:
su versión recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que se benefi1. Si la longitud de la lista es 0 ó 1, entonces ya está cian de la optimización caché.
ordenada. En otro caso:
M.A. Kronrod sugirió en 1969 una versión alternativa del
2. Dividir la lista desordenada en dos sublistas de apro- algoritmo de ordenamiento por mezcla que usaba espacio
adicional constante. Este algoritmo fue refinado por Kaximadamente la mitad del tamaño.
tajainen, Pasanen y Teuhola.
3. Ordenar cada sublista recursivamente aplicando el
ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.
2.3.3 Comparación con otros algoritmos
de ordenamiento
El ordenamiento por mezcla incorpora dos ideas princi- Aunque heapsort tiene los mismos límites de tiempo que
pales para mejorar su tiempo de ejecución:
merge sort, requiere sólo Θ(1) espacio auxiliar en lugar
2.5. HEAPSORT
del Θ(n) de merge sort, y es a menudo más rápido en
implementaciones prácticas. Quicksort, sin embargo, es
considerado por mucho como el más rápido algoritmo
de ordenamiento de propósito general. En el lado bueno,
merge sort es un ordenamiento estable, paraleliza mejor,
y es más eficiente manejando medios secuenciales de acceso lento. Merge sort es a menudo la mejor opción para
ordenar una lista enlazada: en esta situación es relativamente fácil implementar merge sort de manera que sólo
requiera Θ(1) espacio extra, y el mal rendimiento de las
listas enlazadas ante el acceso aleatorio hace que otros
algoritmos (como quicksort) den un bajo rendimiento, y
para otros (como heapsort) sea algo imposible.
(EL PELON)
7
mazo de cartas numeradas en forma arbitraria. Requiere
O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es
un conjunto ordenado. Después, cuando hay k elementos
ordenados de menor a mayor, se toma el elemento k+1 y
se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos
los elementos mayores han sido desplazados una posición
a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
2.4.1 Véase también
Para Perl 5.8, merge sort es el algoritmo de ordenamiento por defecto (lo era quicksort en versiones anteriores de
• Algoritmo de ordenamiento
Perl). En Java los métodos de ordenación de Arrays usan
merge sort o una modificación de quicksort dependiendo
de los tipos de datos y por cuestiones de eficiencia cam- 2.4.2 Enlaces externos
bian a ordenamiento por inserción cuando se están ordenando menos de siete elementos en el array. .,.,
• Distintas implementaciones del algoritmo en Wikibooks (inglés)
2.3.4
Enlaces externos
• Distintas implementaciones del algoritmo en Wikibooks (inglés)
• Distintas implementaciones del algoritmo en RosettaCode.org (inglés)
• Distintas implementaciones del algoritmo en RosettaCode.org (inglés)
2.5 Heapsort
Bibliotecas
• Sort::Merge Módulo Perl en CPAN
• File::MergeSort Módulo Perl en CPAN
2.4 Ordenamiento por inserción
Animación mostrando el funcionamiento del heapsort.
El ordenamiento por montículos (heapsort en inglés) es
un algoritmo de ordenamiento no recursivo, no estable,
con complejidad computacional Θ(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ícuEjemplo de ordenamiento por inserción ordenando una lista de
lo
(cima)
en sucesivas iteraciones obteniendo el conjunto
números aleatorios.
ordenado. Basa su funcionamiento en una propiedad de
El ordenamiento por inserción (insertion sort en los montículos, por la cual, la cima contiene siempre el
inglés) es una manera muy natural de ordenar para un menor elemento (o el mayor, según se haya definido el
ser humano, y puede usarse fácilmente para ordenar un montículo) de todos los almacenados en él. El algoritmo,
8
CAPÍTULO 2. CLASIFICACION
después de cada extracción, recoloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual
destruye la propiedad heap del árbol. Pero, a continuación
realiza un proceso de “descenso” del número insertado de
forma que se elige a cada movimiento el mayor de sus dos
hijos, con el que se intercambia. Este intercambio, realizado sucesivamente “hunde” el nodo en el árbol restaurando la propiedad montículo del arbol y dejándo paso a
la siguiente extracción del nodo raíz.
El algoritmo, en su implementación habitual, tiene dos
fases. Primero una fase de construcción de un montículo
a partir del conjunto de elmentos de entrada, y después,
una fase de extracción sucesiva de la cima del montículo. La implementación del almacén de datos en el heap,
pese a ser conceptualmente un árbol, puede realizarse en
un vector de forma fácil. Cada nodo tiene dos hijos y por
tanto, un nodo situado en la posición i del vector, tendrá a
sus hijos en las posiciones 2 x i, y 2 x i +1 suponiendo que
el primer elemento del vector tiene un índice = 1. Es decir, la cima ocupa la posición inicial del vector y sus dos
hijos la posición segunda y tercera, y así, sucesivamente.
Por tanto, en la fase de ordenación, el intercambio ocurre entre el primer elemento del vector (la raíz o cima del
árbol, que es el mayor elemento del mismo) y el último
elemento del vector que es la hoja más a la derecha en el
último nivel. El árbol pierde una hoja y por tanto reduce
su tamaño en un elemento. El vector definitivo y ordenado, empieza a construirse por el final y termina por el
principio.
2.5.1
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
2.5.2
Enlaces externos
• Distintas implementaciones del algoritmo en Wikibooks (inglés)
• Distintas implementaciones del algoritmo en RosettaCode.org (inglés)
Capítulo 3
Text and image sources, contributors, and
licenses
3.1 Text
• Algoritmo de búsqueda Fuente: http://es.wikipedia.org/wiki/Algoritmo%20de%20b%C3%BAsqueda?oldid=81114917 Colaboradores:
Makz~eswiki, Ascánder, Symonblade, Stan Shebs, Renabot, Caos, Airunp, Taichi, Emijrp, Rembiapo pohyiete (bot), Genba, Drini2, RobotQuistnix, Chobot, Yrbot, GermanX, KnightRider, Jesuja, Facon, Kn, CEM-bot, EnWILLYado, BlackSalamander, FrancoGG, Ggenellina, DominicanZero, MSBOT, Soulbot, DerHexer, Ejconquer, Ofuentesgual, Biasoli, VolkovBot, Technopat, Pmontaldo, Synthebot,
Carmel2007, Edmenb, YonaBot, Cobalttempest, Farisori, Michada~eswiki, Gökhan, AVBOT, MastiBot, DiegoFb, Vic Fede, Jorge Dueñas
Lerín, Xqbot, Jkbw, Botarel, Halfdrag, Dacripo, GrouchoBot, Kasirbot, MerlIwBot, KLBot2, Isacdaavid, Ramzysamman, Crystallizedcarbon, Sergioperezeci y Anónimos: 65
• Algoritmo de agrupamiento Fuente: http://es.wikipedia.org/wiki/Algoritmo%20de%20agrupamiento?oldid=80530746 Colaboradores:
Jjmerelo, Tano4595, Ecemaml, Rembiapo pohyiete (bot), RobotQuistnix, TCrossland~eswiki, FlaBot, BOTijo, Equi, Alfredobi, Thijs!bot,
Cgb, JAnDbot, TXiKiBoT, Juan renombrado, SieBot, Loveless, Juan Mayordomo, AVBOT, Pssuils, Diegusjaimes, Luckas-bot, DiegoFb,
Erud, Xqbot, D'ohBot, EmBOTellado, MondalorBot, Ripchip Bot, EmausBot, ZéroBot, ChuispastonBot, TransportObserver, KLBot2,
Solvete y Anónimos: 14
• Quicksort Fuente: http://es.wikipedia.org/wiki/Quicksort?oldid=82219175 Colaboradores: Pino, Pablo.cl, JorgeGG, Fortran~eswiki, Ascánder, Sms, Tostadora, Jacobo Tarrio, Porao, Renabot, Wariou, Boticario, JMPerez, Rembiapo pohyiete (bot), Human~eswiki, Dem,
CarlosHoyos, RobotQuistnix, Yrbot, YurikBot, Gaboto, GermanX, Gothmog, Joanumbert, BOTpolicia, CEM-bot, Gafotas, Thijs!bot,
JoaquinFerrero, Juen, Xavigivax, Dealonso, Netito777, VolkovBot, Matdrodes, Elabra sanchez, Muro Bot, BotMultichill, DevilishFreak,
SieBot, Loveless, Rafael josem, STBot~eswiki, PipepBot, Yonseca, Eduardosalg, LordT, Chebi~eswiki, Raulshc, Camilo, Paredero,
UA31, Arlm1000, AVBOT, Louperibot, Mkucharuk, DumZiBoT, Papagorila, Manuelt15, Jkbw, Aclapes, Igna, Pandemon~eswiki, Execoot~eswiki, Kelwin, LevanenG, Yago AB, KamikazeBot, Tarawa1943, Savh, J. A. Gélvez, ChuispastonBot, Xerox 5B, Rezabot, JotaMC,
YFdyh-bot, Pepetacos, Addbot, Ambigus9, Milder.q, Jatch21, Holahalou y Anónimos: 134
• Ordenamiento por mezcla Fuente: http://es.wikipedia.org/wiki/Ordenamiento%20por%20mezcla?oldid=81964250 Colaboradores: Xykatra, Ascánder, Sms, Jacobo Tarrio, Boticario, Aeveraal, Rembiapo pohyiete (bot), Dem, RobotQuistnix, Yrbot, FlaBot, BOTijo,
Thijs!bot, Escarbot, JoaquinFerrero, JAnDbot, JulGor, Muro de Aguas, Biasoli, VolkovBot, Aliamondano, Shooke, BotMultichill, SieBot,
PipepBot, DragonBot, UA31, Albambot, AVBOT, Diegusjaimes, Macro.masek, Luckas-bot, Shekatsu8er, ArthurBot, Jkbw, Ricardogpn,
TobeBot, Halfdrag, RedBot, Kelwin, EmausBot, Savh, Grillitus, Paulopin, V!rus, Riemann’sZeta, STANHMAL, Emferr, Addbot, Damnerpalacios, Cfsalguero, Halcydez y Anónimos: 59
• Ordenamiento por inserción Fuente: http://es.wikipedia.org/wiki/Ordenamiento%20por%20inserci%C3%B3n?oldid=82086229 Colaboradores: Pablo.cl, ManuelGR, Sms, Tano4595, Boticario, Rembiapo pohyiete (bot), Drini2, CarlosHoyos, Orgullobot~eswiki, RobotQuistnix, Yrbot, BOTijo, GermanX, Gothmog, Jesuja, Milestones, Kn, CEM-bot, Laura Fiorucci, Thijs!bot, JoaquinFerrero, JAnDbot,
Muro de Aguas, TXiKiBoT, AlnoktaBOT, VolkovBot, Ndarkduck, Technopat, Lahi, Carmel2007, 3coma14, Muro Bot, SieBot, Loveless,
Manuelhosto, Dnu72, HUB, SilvonenBot, AVBOT, MastiBot, Ockie, Diegusjaimes, Arjuno3, InflaBOT, WikiDreamer Bot, XZeroBot,
Albertochoa, Botarel, Josemariovanegas, Fitoschido, Dinamik-bot, Ripchip Bot, ChuispastonBot, Jr JL, Alexsugasti, Addbot, Maub1985
y Anónimos: 114
• Heapsort Fuente: http://es.wikipedia.org/wiki/Heapsort?oldid=74152700 Colaboradores: Dodo, Triku, Ascánder, Sms, Jacobo Tarrio, Taragui, Boticario, Emijrp, Rembiapo pohyiete (bot), RobotQuistnix, Chobot, Yrbot, BOTijo, GermanX, CEM-bot, Santhy, Montgomery,
Thijs!bot, JoaquinFerrero, JAnDbot, Biasoli, VolkovBot, Matdrodes, Elabra sanchez, SieBot, STBot~eswiki, DragonBot, Bgangioni, Louperibot, MelancholieBot, Luckas-bot, Jotterbot, Rotovator, Mcapdevila, Xqbot, Ripchip Bot, J. A. Gélvez, Maucendon, Addbot y Anónimos:
20
3.2 Images
• Archivo:Commons-logo.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/4/4a/Commons-logo.svg Licencia: Public domain
Colaboradores: This version created by Pumbaa, using a proper partial circle and SVG geometry features. (Former versions used to be slightly
9
10
CAPÍTULO 3. TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES
warped.) Artista original: SVG version was created by User:Grunt and cleaned up by 3247, based on the earlier PNG version, created by
Reidab.
• Archivo:Insertion-sort-example-300px.gif
Fuente:
http://upload.wikimedia.org/wikipedia/commons/0/0f/
Insertion-sort-example-300px.gif Licencia: CC BY-SA 3.0 Colaboradores: Trabajo propio Artista original: Swfung8
• Archivo:Merge-sort-example-300px.gif Fuente: http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.
gif Licencia: CC BY-SA 3.0 Colaboradores: Trabajo propio Artista original: Swfung8
• Archivo:Sorting_heapsort_anim.gif Fuente: http://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif Licencia: CC-BY-SA-3.0 Colaboradores: http://de.wikipedia.org/wiki/Image:Sorting_heapsort_anim.gif, own work Artista original: de:User:
RolandH
• Archivo:Sorting_quicksort_anim.gif Fuente: http://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif Licencia: CC-BY-SA-3.0 Colaboradores: originally upload on the English Wikipedia Artista original: Wikipedia:en:User:RolandH
3.3 Content license
• Creative Commons Attribution-Share Alike 3.0