Ordenacion Y Busqueda

ORDENACIÓN Y BÚSQUEDA

Ordenación.

La ordenación o clasificación de datos (sort, en inglés) es una operación consistente en disponer un conjunto de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres; los elementos numéricos se pueden ordenar en orden creciente o decre2ciente de acuerdo al valor numérico del elemento. En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave.

Ordenación Interna

Es cuando los datos están almacenados en un array, una lista enlazada o un árbol.

Ordenación Externa

Es cuando los datos están almacenados en un archivo.

Los métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial atención en su elección.

¿Cómo se sabe cuál es el mejor algoritmo? La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, dos criterios se suelen seguir a la hora de decidir qué algoritmo es el más eficiente:

1) tiempo menor de ejecución en computadora;

2) menor número de instrucciones.

Sin embargo, no siempre es fácil efectuar estas medidas, ya que las instrucciones pueden variar, dependiendo del lenguaje y del propio estilo del programador. Por esta razón, el mejor criterio para medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y contar el número de veces que se realiza. Así, en el caso de los algoritmos de ordenación, se utilizará como medida de su eficiencia el número de comparaciones entre elementos efectuados. El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.

Los métodos de ordenación se suelen dividir en dos grandes grupos:

• Directos: burbuja, selección, inserción , intercambio

• Indirectos (avanzados): Shell, ordenación rápida, ordenación por mezcla,

En el caso de listas pequeñas, los métodos directos se muestran eficientes, sobre todo porque los algoritmos son sencillos; su uso es muy frecuente. Sin embargo, en listas grandes estos métodos se muestran ineficaces y es preciso recurrir a los métodos avanzados.

Ordenación por Intercambio

El algoritmo de ordenación tal vez más sencillo sea el denominado de intercambio que ordena los elementos de una lista en orden ascendente. Este algoritmo se basa en la lectura sucesiva de la lista a ordenar, comparando el elemento inferior de la lista con los restantes y efectuando intercambio de posiciones cuando el orden resultante de la comparación no sea el correcto.

El algoritmo realiza n − 1 pasadas, siendo n el número de elementos, y ejecuta las siguientes operaciones:

El elemento de índice 0 (a[0]) se compara con cada elemento posterior de la lista de índices 1, 2 y 3. En cada comparación se comprueba si el elemento siguiente es más pequeño que el elemento de índice 0, en ese caso se intercambian. Después de terminar todas las comparaciones, el elemento más pequeño se localiza en el índice 0.

Pasada 1

Pasada 2

Algoritmo en C

Ordenación por Selección

Considérese el algoritmo para ordenar un array A de enteros en orden ascendente, es decir, del número más pequeño al mayor. Es decir, si el array A tiene n elementos, se trata de ordenar los valores del array de modo que el dato contenido en A[0] sea el valor más pequeño, el valor almacenado en A[1] el siguiente más pequeño, y así hasta A[n-1], que ha de contener el elemento de mayor valor. El algoritmo se apoya en sucesivas pasadas que intercambian el elemento más pequeño sucesivamente con el primer elemento de la lista, A[0] en la primera pasada. En síntesis, se busca el elemento más pequeño de la lista y se intercambia con A[0], primer elemento de la lista.

A[0] A[1] A[2] .... A[n-1]

Después de terminar esta primera pasada, el frente de la lista está ordenado y el resto de la lista A[1], A[2]...A[n-1] permanece desordenado. La siguiente pasada busca en esta lista desordenada y selecciona el elemento más pequeño, que se almacena entonces en la posición A[1]. De este modo los elementos A[0] y A[1] están ordenados y la sublista A[2], A[3]...A[n-1] desordenada; entonces, se selecciona el elemento más pequeño y se intercambia con A[2]. El proceso continúa n − 1 pasadas y en ese momento la lista desordenada se reduce a un elemento (el mayor de la lista) y el array completo ha quedado ordenado.

Algoritmo en C

Ordenación por Inserción

El método de ordenación por inserción es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste en insertar un nombre en su posición correcta dentro de una lista o archivo que ya está ordenado. Así el proceso en el caso de la lista de enteros

A = 50, 20, 40, 80, 30.

Algoritmo en C

Ordenación por Burbuja

El método de ordenación por burbuja es el más conocido y popular en programación, por su facilidad de comprensión y programación; por el contrario, es el menos eficiente y por ello, normalmente, se aprende su técnica pero no suele utilizarse.

La técnica utilizada se denomina ordenación por burbuja u ordenación por hundimiento debido a que los valores más pequeños «burbujean» gradualmente (suben) hacia la cima o parte superior del array de modo similar a como suben las burbujas en el agua, mientras que los valores mayores se hunden en la parte inferior del array. La técnica consiste en hacer varias pasadas a través del array. En cada pasada, se comparan parejas sucesivas de elementos. Si una pareja está en orden creciente (o los valores son idénticos), se dejan los valores como están. Si una pareja está en orden decreciente, sus valores se intercambian en el array.

Algoritmo en C

El algoritmo terminará, bien cuando se termine la última pasada (n − 1) o bien cuando el valor del interruptor sea falso (0), es decir, no se haya hecho ningún intercambio. La condición para realizar una nueva pasada se define en la expresión lógica

TAREA: Implemente cada uno de los métodos exlicados anteriormente en python usando funciones

...