claces

Leissi M. Castañeda León
lcl@upnorte.edu.pe
https://sites.google.com/site/leissicl/

1.
2.

Introducción
Ordenación Interna
Ordenación por intercambio directo (Burbuja)
Ordenación por el método de intercambio directo con señal
Ordenación por el método de la sacudida (shaker sort)
Ordenación por inserción directa
Ordenación por el método de inserción binaria
Ordenación por seleccióndirecta
Ordenación por el método de Shell
Ordenación por el método QuickSort
Ordenación por el método HeapSort (montículo)

3.

Ordenación Externa

ORDENAR significa reagrupar o reorganizar un conjunto
de datos u objetos en un secuencia específica.
Los procesos de ordenación y búsqueda son frecuentes
en nuestra vida. Vivimos en un mundo desarrollado,
automatizado, acelerado, dondela información
representa un elemento de vital importancia.
Los objetos ordenado aparecen por doquier: Directorio
telefónico, registros de pacientes de un hospital,
registros de huéspedes de un hotel, listados de alumnos
en una clase, índice de libros en una biblioteca, etc.; son
tan sólo algunos ejemplos.

¿Cuándo es conviente usar un método de
ordenación?
Rpta: Cuando se requiere haceruna cantidad
considerable de búsquedas y es importante el factor
tiempo.
Imagine que ocurriría si se deseara encontrar un libro en
una biblioteca con más de 100 000 volúmenes y éstos
estuvieran desordenados o registrados en el orden en el
que fueron reciibidos.

Formalmente se define ordenación de la siguiente
manera:
Sea A una lista de N elementos:
A1, A2, A3,..., AN
Ordenarsignifica permutar estos elementos de tal forma
que los mismos queden de acuerdo con una distribución
preestablecida.
Ascendente: A1 ≤ A2 ≤ A3 ≤ … ≤ AN
Descendente: A1 ≥ A2 ≥ A3 ≥ ... ≥ AN

En el procesamiento de datos, a los métodos de
ordenación se les clasifica en dos grandes categorías,
según donde hayan sido almacenados:
Ordenación de arreglos
Ordenación de archivos

La primeracategoría se denomina también ordenación
interna (dado que los elementos del arreglo se
encuentran en memoria principal) y la segunda
ordenación externa (dado que los elementos se
encuentra en archivos almacenados en dispositivos de
almacenamiento secundario, como: discos, cintas, etc.)

Se podría decir que para la máquina:
Ordenación Interna: representa lo que para un humano
significa ordenar unconjunto de cartas que se
encuentran todas visibles y extendidas sobre la mesa.
Ordenación Externa: representa lo que para un humano
significa ordenar cartas que están dispuestas una
debajo otra y en donde sólo se visualiza la primera.

!

"

Se explicarán con arreglos unidimensionales, pero su
uso puede extenderse a otros tipos de arreglos y
estructuras de datos.
Dentro de laordenación interna los métodos se
clasifican en dos tipos:
Métodos directos: tienen la característica de que su
implementación es relativamente sencilla y de fácil comprensión,
aunque son ineficientes cuando N (el número de elementos del
arreglo) es medio o grande.
Métodos logarítmicos: son más complejos que los directos. Su
elaboración es más sofisticada y, al ser menos intuitivo (másabstracta), resultan más difíciles de entender. Pero son más
eficientes cuando el número de elementos es medio o grande.
#

Notar que la eficiencia entre los distintos métodos va
estar dada por el tiempo de ejecución (depende del
número de comparaciones y movimientos).
Los métodos directos más conocidos son:
Ordenación por intercambio
Ordenación por inserción
Ordenación por selección

$%!$!

&
'
() ' * +

$$

&

'

() ' * +
Es el más utilizado entre los estudiantes principiantes de
computación por su fácil comprensión y programación.
Se podría señalar que es quizás el método más
ineficiente.
2 formas:
Llevando los elementos menores a la izquierda: Burbuja Menor
Llevando los elementos mayores a la derecha: Burbuja Mayor

Al final de las (n-1) pasadas, los...