UNIVERSIDAD NACIONAL DEL SANTA
Escuela Profesional de Ingeniería de Sistemas e Informática
METODOS DE
ORDENAMIENTO
Mag. Hugo Esteban Caselli Gismondi
2021-II
¿QUÉ ES ORDENAMIENTO?
Es la operación de organizar datos en algún orden
secuencial de acuerdo a un criterio que puede ser
creciente o decreciente para los números o
ascendente o descendente (alfabéticamente) para
datos de caracteres. El propósito principal de un
ordenamiento es el de facilitar las búsquedas de los
miembros del conjunto ordenado.
Ejemplos de ordenamientos: Directorios telefónicos,
índices de contenidos, bibliotecas y diccionarios, etc.
Tipos de ordenamientos: interno y externos
a) Internos
Son aquellos en los que los valores a ordenar están en memoria
principal, por lo que se asume que el tiempo que se requiere para
acceder cualquier elemento sea el mismo. Se agrupan de la siguiente
manera:
– Algoritmos de Inserción
Cada elemento es INSERTADO en la posición apropiada con respecto al
resto de los elementos ya ordenados: Inserción directa, binaria, Shell.
Tipos de ordenamientos: interno y externos
– Algoritmos de Intercambio
En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y si
no están en el orden adecuado se INTERCAMBIAN. Este proceso se repite hasta que
se ha analizado todo el conjunto de elementos y ya no hay intercambios: Burbuja,
Quick sort.
– Algoritmos de Selección
En este tipo de algoritmos se SELECCIONA o se busca el elemento menor valor (o
mayor valor) de todo el conjunto de elementos y se coloca en su posición adecuada.
Este proceso se repite para el resto de los elementos hasta que todos son
analizados: Selección directa.
Tipos de ordenamientos: internos y externos
b) Externos
Son aquellos en los que los valores a ordenar están en memoria
secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume
que el tiempo que se requiere para acceder a cualquier elemento
depende de la última posición accesada: Straight merging, Natural
merging, Balanced multiway merging, Polyphase sort, Distribution of
initial runs.
Eficiencia en tiempo de ejecución
Una medida de eficiencia es contar el número de
comparaciones (C), contar el número de movimientos de
ítems (M), estos están en función del número (n) de ítems a
ser ordenados, se toma n como el número de elementos
que tiene el arreglo o vector a ordenar y se dice que un
algoritmo realiza O(n2) comparaciones cuando compara n
veces los n elementos, n x n = n2
Método de Inserción Directa
Este método toma cada elemento del arreglo para ser ordenado y lo
compara con los que se encuentran en posiciones anteriores a la de
él dentro del arreglo. Si resulta que el elemento con el que se está
comparando es mayor que el elemento a ordenar, se recorre hacia
la siguiente posición superior. Si por el contrario, resulta que el
elemento con el que se está comparando es menor que el elemento
a ordenar, se detiene el proceso de comparación pues se encontró
que el elemento ya está ordenado y se coloca en su posición (que es
la siguiente a la del último número con el que se comparó).
Método de Inserción Directa (2)
Este procedimiento recibe el arreglo de datos a ordenar A[ ] y altera las posiciones
de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el
número de elementos que contiene A[ ]. Pseudocódigo:
INICIO
A[0] -999
N 8; K 2
Repetir hasta K=N
TEMP A[K]
PTR K-1
Repetir mientras TEMP<A[PTR]
A[PTR+1] A[PTR]
PTR PTR-1
Fin repetir mientras
A[PTR+1] TEMP
K K+1
Fin repetir hasta
FIN
Método de Selección
Consiste en encontrar el menor de todos los elementos del arreglo e
intercambiarlo con el que está en la primera posición. Luego el segundo más
pequeño, y así sucesivamente hasta ordenar todo el arreglo. Pseudocódigo:
INICIO
Repetir K desde 1 hasta N-1
MIN A[K]
POS K
Repetir J desde K+1 hasta N
Si MIN > A[J] entonces
MIN A[J]
POS J
Fin_si
Fin repetir desde_J
TEMP A[K]; A[K] A[POS]; A[POS] TEMP
Fin repetir desde_K
FIN
Método de la Burbuja
El bubble sort, también conocido como ordenamiento burbuja,
funciona de la siguiente manera: Se recorre el arreglo
intercambiando los elementos adyacentes que estén desordenados.
Se recorre el arreglo tantas veces hasta que ya no haya cambios.
Prácticamente lo que hace es tomar el elemento mayor (o menor) y
lo va recorriendo de posición en posición hasta ponerlo en su lugar.
Método de Shell
Ordenamiento de disminución incremental. Nombrado así debido a
su inventor Donald Shell. Ordena subgrupos de elementos
separados K unidades (respecto de su posición en el arreglo) del
arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados
(generalmente utilizando INSERCION DIRECTA), se escoge un nuevo
valor de K más pequeño, y el arreglo es de nuevo partido entre el
nuevo conjunto de subgrupos.
Método de Shell (2)
Cada uno de los subgrupos mayores es ordenado y el proceso se
repite de nuevo con un valor más pequeño de K. Eventualmente el
valor de K llega a ser 1, de tal manera que el subgrupo consiste de
todo el arreglo ya casi ordenado. Al principio del proceso se escoge
la secuencia de decrecimiento de incrementos; el último valor debe
ser 1. "Es como hacer un ordenamiento de burbuja pero
comparando e intercambiando elementos“.
Método de Shell (3)
Cuando el incremento toma un valor de 1, todos los elementos
pasan a formar parte del subgrupo y se aplica inserción directa. El
método se basa en tomar como salto N/2 (siendo N el número de
elementos) y luego se va reduciendo a la mitad en cada repetición
hasta que el salto o distancia vale 1.
Búsqueda
La búsqueda es una de las operaciones que aparecen con más frecuencia
en programación de ordenadores. Básicamente, se trata de hallar un
elemento determinado dentro de una colección de N datos, que
generalmente se representa mediante una estructura de tipo vector A[N],
donde los tipo de datos pueden ser entero, real, etc. Esto significa, que
dado un argumento de búsqueda, X, se trata de encontrar el índice i del
vector A para el cual se verifica A(i)=X.
a) Búsqueda Lineal
Es la solución más obvia y que se aplica cuando no hay ninguna
información adicional acerca de los datos buscados. Consiste en
recorrer secuencialmente el vector hasta encontrar el dato buscado,
siendo por tanto las condiciones de parada: A(i)=X se halló el
elemento buscado o i=N se llegó al final del vector. Se debe
comprobar después si la operación tuvo éxito, o simplemente se llegó
al final del vector.
a) Búsqueda Lineal (2)
Pseudocódigo
INICIO
POS 0
Repetir desde i = 1 hasta N
Si A[ i ] = t entonces
POS i
Fin_si
Fin repetir desde
FIN
b) Búsqueda Binaria
La operación de búsqueda puede ser mucho más eficiente si se sabe
que los datos están previamente ordenados. Basta considerar como
ejemplo un diccionario, en el que hacemos una búsqueda gracias a la
ordenación alfabética de las palabras. En otro caso, sería algo
completamente inutilizable.
La idea clave consiste en inspeccionar un elemento cualquiera, de índice m
(normalmente en la mitad), y compararlo con el argumento X.
b) Búsqueda Binaria (2)
Los posibles casos son:
A(m)=X.- ha terminado la búsqueda y el índice buscado es m
A(m)<X.- sabemos que todos los elementos a la izquierda de m son menores
que X, y por tanto pueden ser eliminada esta región de la zona de búsqueda y
considerar sólo la zona derecha (desde m+1 hasta N)
A(m)>X.- sabemos que todos los elementos a la derecha de m son mayores que
X, y considerar para la búsqueda sólo la zona izquierda (desde 1 hasta m-1)
La repetición de este proceso de forma iterativa constituye este algoritmo. Para
ello, se utilizan dos variables de índice, I y D, que marcan los extremos Izquierdo
y Derecho de la zona de búsqueda considerada.
b) Búsqueda Binaria (2) Pseudocódigo
INICIO
Leer X
i 1; j n – 1; m (i+j) \ 2
Mientras (a[m] <> X y i<j) hacer
Si X < a[m] entonces j m-1
caso contrario i m+1
Fin_si
m (i+j) \ 2
Fin mientras
Si i >= j entonces Escribir “Dato buscado no se encuentra”
caso contrario Escribir “Dato fue encontrado en posición”+m ;
Fin_si
FIN
Referencias Bibliográficas
■ Joyanes Aguilar, L. (2003). Fundamentos de Programación:
Algoritmos, Estructuras de datos y Objetos. Madrid: McGraw-Hill. (Vol.
Código biblioteca UNS: 005.1 J79)..
■ Baase, S., & Gelder, A. (2002). Algoritmos computacionales.
Introducción al análisis y diseño. México: Pearson Educación. (Vol.
Código Biblioteca UNS: 005.1 C16)
