ALGORITMOS DE ORDENACIÓN Y BÚSQUEDA

octubre 1, 2007

ALGORITMOS DE ORDENACIÓN Y BÚSQUEDA EN

VECTORES.

1. Algoritmos de ordenación y búsqueda en vectores:

            1.1 Ordenación de vectores:

 

Ordenar un vector se trata de reorganizar sus elementos según alguna relación de orden. El objetivo de la ordenación es que la información se pueda recuperar fácil y rápidamente (por ejemplo, en una base de datos grande). La ordenación es bastante usual en programación, existiendo varios métodos o algoritmos distintos de ordenación. Cuando se selecciona el método a usar, debe tenerse en cuenta la eficacia del mismo en dos aspectos:

 

• En la memoria que utiliza

• En el tiempo de ejecución

 

Si N es el número de elementos que se quiere ordenar, los buenos algoritmos de ordenación realizan del orden de Nlog 2 N operaciones. En esta práctica vamos a estudiar algunos algoritmos que realizan del orden de N 2   operaciones. Son métodos directos, que son más cortos y fáciles de entender, de tal forma que si N es pequeño, son lo suficientemente eficaces.

 

1.1.1 Algoritmo de intercambio directo (burbuja)

 

Básicamente consiste en realizar varias iteraciones que llevan el elemento menor del vector hasta su posición. Se considera el vector dividido en dos partes la parte ordenada y la parte desordenada. Inicialmente, se considera que todo el vector está desordenado. Se detecta el elemento menor del vector y se lleva a la posición más a la izquierda posible, quedando por tanto colocado en su posición definitiva. El elemento que estaba en ese extremo de la izquierda se desplaza, junto con los demás, hacia la derecha, hasta llegar donde estaba el elemento menor. Este método también se conoce como “método de la burbuja” ya que si imaginamos el vector en posición vertical y considerando los elementos como burbujas con “pesos” en proporción a su valor, en cada pasada sobre el vector ascenderá hasta el nivel superior la “burbuja” de menor peso, desplazando a las demás hacia abajo.

 

 

1.2 Algoritmos de búsqueda:

 

Existen dos métodos básicos de búsqueda de un elemento en un vector: lineal y binaria. La búsqueda lineal ya se ha estudiado en Fundamentos de Informática, y en ella no hace falta que el vector esté ordenado. El algoritmo de búsqueda binaria requiere que el vector esté ordenado. Consiste en situarse en el elemento central del vector, comparando el elemento buscado con el elemento central. Si coincide, se ha terminado la búsqueda con éxito. Si el elemento a buscar es menor, rechazamos los elementos de la derecha, si es mayor, rechazaremos los elementos de la izquierda, y así  sucesivamente. El algoritmo puede expresarse en C como sigue, donde se supone que este código forma parte de una función que devuelve –1 si la variable dato no se encuentra en el vector, y el índice correspondiente en caso contrario.

 

 

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: