Fichas Bibliofraficas

TEMA. 3

METODOS DE ORDENACIÓN Y BUSQUEDA

Introducción

Generalmente, se considera ordenar (clasificar) el proceso de reorganización de un conjunto dado de objetos en una secuencia especificada. El objetivo de este proceso es facilitar la búsqueda posterior de los elementos del conjunto ordenado. La búsqueda de información es una operación básica en el proceso de datos, de ahí que por extensión, la ordenación se convierta también en una actividad fundamental en dicho procesamiento de datos.

La vida cotidiana está llena de ejemplos donde la ordenación de información facilita enormemente nuestros procesos habituales de búsqueda, por ejemplo, las guías de teléfonos, los índices de libros, los diccionarios, etc.

El tema de ordenación es idóneo para mostrar como los problemas se pueden resolver utilizando una gran variedad de algoritmos, normalmente, la clasificación se divide en interna o externa. El concepto de ordenación interna hace referencia a que el soporte donde se realiza la ordenación es la memoria principal del ordenador. Cuando el número de elementos que se desea clasificar es demasiado grande para caber en memoria y se encuentra en un fichero, entonces se habla de ordenación externa.

En este tema se tratara exclusivamente el problema de la ordenación interna.

Desde el punto de vista formal, ordenar consiste en permutar una secuencia de elementos:

A[1], A[2], ... , A[n] para obtener otra secuencia,

A[k1], A[k2], ... , A[kn]

de forma que, dada una función de ordenación f, se verifique:

f(A[k1]) <= f(A[k2]) <= ... <= f(A[kn])

Normalmente, la función de ordenación viene explícitamente reflejada en los objetos a ordenar como un campo de información mas sobre cada elemento. De manera que, en general, cada elemento del conjunto tendrá más de un campo de información (estructura de registro) y uno de esos campos indicará como se clasifican los elementos. El campo que especifica la relación de orden recibe el nombre de clave. El problema de la clasificación consiste entonces en ordenar una secuencia de registros de manera que sus claves formen una cadena no decreciente.

Existen varios métodos de ordenación, por ejemplo:

• Método de la burbuja

• Método de selección

• Método de inserción

• Método Shell

• Método del Quicksort

• Método de ordenación por intercambio directo

De los cuales estudiaremos los cuatro primeros y el resto se deja como trabajo de consulta al estudiante.

Método 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 que va recorriendo de posición en posición hasta ponerlo en su lugar.

Procedimiento Burbuja

Paso 1: [Inicializa i al final de arreglo] For i = N down to 1 do

Paso 2: [Inicia desde la segunda pos.] For j = 2 to i do

Paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] > a[j] then

Paso 5: [Los intercambia] Swap(a, j-1, j).

Paso 7: [Fin] End.

Método de selección.

El método de ordenamiento por 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 mas pequeño e intercambiarlo con el que esta en la 2da posicion, y así sucesivamente hasta ordenar todo el arreglo.

Procedimiento Selection

Paso 1: [Para cada pos. del arreglo] For i = 1 to N do

Paso 2: [Inicializa la pos. del menor] menor = i

Paso 3: [Recorre todo el arreglo] For j = i+1 to N do

Paso 4: [Si a[j] es menor] If a[j] < a[menor] then

Paso 5: [Reasigna el apuntador al menor] min = j

Paso 6: [Intercambia los datos de la pos. min y posición i] Swap(a, min, j).

Paso 7: [Fin] End.

Ejemplo:

El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].

Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.

Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].

El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'.

El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].

...