ORDENAMIENTO.
Uno de los procedimientos más comunes y útiles en el procesamiento
de datos, es la clasificación u ordenación de los mismos. Se considera ordenar
al proceso de reorganizar un conjunto dado de objetos en una secuencia
determinada. Cuando se analiza un método de ordenación, hay que determinar
cuántas comparaciones e intercambios se realizan para el caso más favorable,
para el caso medio y para el caso más desfavorable.
La colocación en orden de una lista de valores se llama Ordenación.
Por ejemplo, se podría disponer una lista de valores numéricos en orden
ascendente o descendente, o bien una lista de nombres en orden alfabético. La
localización de un elemento de una lista se llama búsqueda.
Tal operación se puede hacer de manera más eficiente después de que
la lista ha sido ordenada.
Existen varios métodos para ordenamiento, clasificados en tres
formas:
Intercambio
Selección
Inserción.
En cada familia se distinguen dos versiones: un método simple y
directo, fácil de comprender pero de escasa eficiencia respecto al tiempo de
ejecución, y un método rápido, más sofisticado en su ejecución por la
complejidad de las operaciones a realizar, pero mucho más eficiente en cuanto a
tiempo de ejecución. En general, para arreglos con pocos elementos, los métodos
directos son más eficientes (menor tiempo de ejecución) mientras que para
grandes cantidades de datos se deben emplear los llamados métodos rápidos.
Intercambio
El método de intercambio se basa en comparar los elementos del
arreglo e intercambiarlos si su posición actual o inicial es contraria inversa
a la deseada. Pertenece a este método el de la burbuja clasificado como
intercambio directo. Aunque no es muy eficiente para ordenar listas grandes, es
fácil de entender y muy adecuado para ordenar una pequeña lista de unos 100
elementos o menos.
Una pasada por la ordenación de burbujeo consiste en un recorrido
completo a través del arreglo, en el que se comparan los contenidos de las
casillas adyacentes, y se cambian si no están en orden. La ordenación por burbujeo
completa consiste en una serie de pasadas ("burbujeo") que termina
con una en la que ya no se hacen cambios porque todo está en orden.
Ejemplo:
Supóngase que están almacenados cuatro números en un arreglo con
casillas de memoria de x[1] a x[4]. Se desea disponer esos números en orden
creciente. La primera pasada de la ordenación por burbujeo haría lo siguiente:
Comparar el contenido de x[1] con el de x[2]; si x[1] contiene el
mayor de los números, se intercambian sus contenidos.
Comparar el contenido de x[2] con el de x[3]; e intercambiarlos si
fuera necesario.
Comparar el contenido de x[3] con el de x[4]; e intercambiarlos si
fuera necesario.
Al final de la
primera pasada, el mayor de los números estará en x[4].
Quicksort.
Si bien el método de la burbuja era considerado como el peor método
de ordenación simple o menos eficiente, el método Quicksort basa su estrategia
en la idea intuitiva de que es más fácil ordenar una gran estructura de datos
subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre
ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de
forma que los elementos del subarray inferior sean más pequeños que los del
subarray superior, y aplicamos el método reiteradamente, al final tendremos el array
inicial totalmente ordenado. Existen además otros métodos conocidos, el de
ordenación por montículo y el de shell.
Selección
Los métodos de ordenación por selección se basan en dos principios
básicos:
Seleccionar el elemento más pequeño (o más grande) del arreglo.
Colocarlo en la posición más baja (o más alta) del arreglo.
A diferencia del método de la burbuja, en este método el elemento
más pequeño (o más grande) es el que se coloca en la posición final que le
corresponde.
Inserción.
El fundamento de este método consiste en insertar los elementos no
ordenados del arreglo en subarreglos del mismo que ya estén ordenados.
Dependiendo del método elegido para encontrar la posición de inserción
tendremos distintas versiones del método de inserción.
BÚSQUEDA.
La búsqueda es una operación que tiene por objeto la localización de
un elemento dentro de la estructura de datos. A menudo un programador estará
trabajando con grandes cantidades de datos almacenados en arreglos y pudiera
resultar necesario determinar si un arreglo contiene un valor que coincide con
algún valor clave o buscado.
Siendo el array de una dimensión o lista una estructura de acceso
directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan
estos dos métodos de acceso, para encontrar elementos dentro de un array:
búsqueda lineal y búsqueda binaria.
Búsqueda
Secuencial:
La búsqueda secuencial es la técnica más simple para buscar un
elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e
ir comparando con el valor buscado (clave). Se empieza con la primera casilla
del arreglo y se observa una casilla tras otra hasta que se encuentra el
elemento buscado o se han visto todas las casillas. El resultado de la búsqueda
es un solo valor, y será la posición del elemento buscado o cero. Dado que el
arreglo no está en ningún orden en particular, existe la misma probabilidad de
que el valor se encuentra ya sea en el primer elemento, como en el último. Por
lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la
mitad de los elementos del arreglo.
El método de
búsqueda lineal funciona bien con arreglos pequeños o para arreglos no
ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta
velocidad de búsqueda binaria, donde se reduce sucesivamente la operación
eliminando repetidas veces la mitad de la lista restante.
Búsqueda Binaria.
La búsqueda binaria es el método más eficiente para encontrar
elementos en un arreglo ordenado. El proceso comienza comparando el elemento
central del arreglo con el valor buscado. Si ambos coinciden finaliza la
búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido
estricto que el central del arreglo. Si el elemento buscado es mayor se procede
a hacer búsqueda binaria en el subarray superior, si el elemento buscado es
menor que el contenido de la casilla central, se debe cambiar el segmento a
considerar al segmento que está a la izquierda de tal sitio central.
No hay comentarios:
Publicar un comentario