Metodo de ordenamiento y de busqueda

METODO DE ORDENAMIENTO Y DE BUSQUEDA

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 realizanpara 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 maneramá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 lasoperaciones 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 suposició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 secomparan 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 ordencreciente. 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 primerapasada, el mayor de los números estará en x[4].
[pic]

[pic]

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 otraspalabras, 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 dosprincipios 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...