Algoritmos

Capítulo 14. Algoritmos de ordenación y de búsqueda.

1. Introducción.

2. Métodos de ordenación.
2.1. Método de inserción directa.
2.2. Método de selección directa.
2.3. Método de intercambio directo o de la burbuja.
2.4. Método Quicksort.

3. Métodos de búsqueda.
3.1. Búsqueda directa.
3.2. Búsqueda directa con datos ordenados.
3.3. Búsqueda binaria o dicotómica.


1.Introducción.
Uno de los procesos más usuales en el tratamiento de datos es la ordenación de los mismos. Lógicamente, los datos se ordenan para acelerar su posterior localización.

Cuando el criterio de ordenación se basa en una variable numérica, obviamente un número es mayor que otro si su valor es más grande. Cuando se trata de una variable alfanumérica, una será mayor que otra si por ordenalfabético es posterior. Debe recordarse que el orden que se aplica es el establecido en el código ASCII. Por ejemplo, el carácter ‘d’ es mayor que el ‘Z’, ya que las mayúsculas son todas menores que las minúsculas. Por otra parte, para comparar cadenas de caracteres tenemos la función strcmp() que fue explicada en un capítulo anterior.

La búsqueda de un dato dentro de un conjunto es otro de losprocesos más habituales en el tratamiento de información. Como vamos a ver, si los datos están ordenados, la localización de uno de ellos puede acelerarse.

2. Métodos de ordenación.
En todos los métodos que vamos a comentar se supone que tenemos un array de N elementos y lo queremos ordenar de menor a mayor. El índice del array se moverá entre 0 y N-1.

Estos métodos podrán aplicarse aestructuras de datos diferentes de los arrays, como por ejemplo los registros de un fichero, siendo el algoritmo idéntico y cambiando simplemente los nombres de algunas variables.

2.2. Método de inserción directa.
Consiste en buscar para cada elemento, desde el elemento 0 en adelante, el puesto que le corresponde entre los elementos ya ordenados. Cuando se va a localizar el puesto del elemento i,los elementos anteriores del 0 al i-1 ya estarán ordenados.

El proceso sería:

- i vale 0: cuando sólo se considera un elemento (valor 19), está en su puesto.

i=0 1 2 3 4
19 5 13 4 7

- i pasa a 1: consideramos dos elementos; se busca el puesto del elemento i, es decir del elemento 1 (valor 5); si el puesto es el 0, se desplaza el elemento 0 (valor 19) una posición, insertando elelemento 1 en la posición 0.

0 i=1 2 3 4
5 19 13 4 7

- i pasa a 2: consideramos 3 elementos; se busca el puesto del elemento i, es decir del elemento 2 (valor 13); el puesto se busca desde la posición 0 hasta la i-1, o sea desde 0 a 1; al 13 le corresponde el puesto 1, por lo que se desplaza desde esa posición hasta i los elementos del array (sólo el 19 en este ejemplo) y se inserta el 13 en laposición 1.

0 1 i=2 3 4
5 13 19 4 7

- i pasa a 3: consideramos 4 elementos; se busca el puesto del elemento i, es decir del elemento 3 (valor 4); el puesto se busca desde la posición 0 hasta la i-1, o sea desde 0 a 2; al 4 le corresponde el puesto 0, por lo que se desplaza desde esa posición hasta i los elementos del array (el 5, el 13 y el 19 en este ejemplo) y se inserta el 4 en laposición 0.

0 1 2 i=3 4
4 5 13 19 7

- i pasa a 4: consideramos 5 elementos; se busca el puesto del elemento i, es decir del elemento 4 (valor 7); el puesto se busca desde la posición 0 hasta la i-1, o sea desde 0 a 3; al 7 le corresponde el puesto 2, por lo que se desplaza desde esa posición hasta i los elementos del array (el 13 y el 19 en este ejemplo) y se inserta el 7 en la posición 2.

0 1 23 i=4
4 5 7 13 19

- i pasa a 5: como i es igual a N (el número de elementos del array), ya finaliza el proceso.

Por tanto, se trata de buscar el puesto de N elementos, es decir un bucle de N iteraciones (i de 0 a N-1). Para cada iteración, es decir para cada elemento i, debe buscarse su puesto recorriendo el array hasta i, o sea este bucle usará una j desde 0 a i. Cuando se conozca el...