Ordenación Y búsqueda.

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación

Universidad Experimental De Guayana

Ingeniería Industrial

Semestre 2014-I

Computación II.

Ordenación y búsqueda

Profesor: Integrantes:

Luis Estraño G. Abel Guzman

Royce Romero

Christian Zacarias

Puerto Ordaz, junio de 2014

Métodos de Ordenamiento

Muchas veces es necesario además de buscar elementos dentro de en un vector, ordenarlos. Este ordenamiento puede ser de mayor a menor si estamos manejando números y en orden alfabético si se trata de nombres o caracteres. Existe una gran variedad de métodos de ordenamiento que nos permiten organizar con rapidez los elementos que se encuentran dentro de un vector o archivo. La elección de un determinado método de ordenamiento depende de el tamaño del vector que se desea ordenar. Entre los métodos de ordenamiento mas populares encontramos: Burbuja, Intercambio, selección, shell, quick-sort, etc. Para entender el concepto de los métodos de ordenamiento en este documento desarrollaremos un ejercicio, en donde se implementan tres de los métodos mencionados para ordenar un vector de números enteros.

Método de ordenamiento por Burbuja:

Este método consiste en comparar los elementos del arreglo que se encuentran en posiciones adyacentes empezando desde la primera posición y llegando hasta el final del arreglo. La comparación dependerá si estamos ordenando el arreglo en forma ascendente o descendente. Para el caso de ordenamiento ascendente (de menor a mayor) se compara cada elemento con el que le sigue inmediatamente usando el operador mayor que (>).

Si el elemento de la posición de la izquierda es mayor que el elemento de la posición que le sigue a su derecha, entonces los dos elementos están mal ubicados y procedemos a intercambiarlos de posición.

El proceso empieza entonces comparando los elementos de la posiciones 1 y 2 del vector, haciendo el intercambio si es preciso. Luego se comparan los elementos de las posiciones 2 y 3 y se procede de igual manera. Seguidamente se comparan los elementos de las posiciones restantes del vector y se realiza el intercambio si es necesario. Se continua así hasta comparar los elementos de las ultimas dos posiciones. Al llegar a este punto resulta que el valor mayor del arreglo quedara ubicado en la última posición del mismo, es decir estará en su posición correcta.

El proceso se repite de nuevo iniciando otra vez desde la posición 1 del vector, pero teniendo en cuenta que como ya acomodamos en la posición correcta el mayor elemento, la ultima comparación que se hará será entre los elementos de las posiciones penúltima y antepenúltima. Es decir, que reducimos en uno el número de comparaciones hechas para acomodar el primer elemento.

Implementación del método que intercambia los elementos de dos posiciones del vector, este método se utilizara para mostrar la implementación de los otros dos métodos de ordenamiento:

procedure TOrdenamientos.cambiar(p1, p2: integer);

var

temp:integer;

begin

temp:=vector[p1];

vector[p1]:=vector[p2];

vector[p2]:=temp;

end;

Método de ordenamiento por selección:

Este método busca el elemento de menor valor dentro del vector y lo coloca en la primera posición, luego busca el segundo elemento mas pequeño y procede a colocarlo en la segunda posición del vector, esto se repite hasta que se ordenan todos los elementos del vector.

Para la implementación de este método primero buscamos la posición del elemento mas pequeño del vector y se realiza el intercambio con el primer elemento del vector. Luego se buscan los elementos restantes hasta que solo quede el mayor.

Implementación del método auxiliar para buscar la posición del elementomas pequeño del vector y realizar el intercambio:

function TOrdenamientos.posMenor(inicio: integer): integer;

var

i:integer; //Variable que controla el ciclo que recorre el vector para obtener el elemento menor.

pMin:integer; //variable para establecer la posición del elemento menor.

min:integer; //variable para representar el elemento menor del vector.

begin

pMin:=inicio;

min:=getVector(inicio);

for i:=inicio+1 to num do

begin

//compara si el elemento de la derecha es menor que el elemento anterior (izquierda). if getVector(i) < min then

begin

min:=getVector(i);

pMin:=i;

end;

end;

//El método devuelve la posición en donde esta el elemento menor del vector para realizar el intercambio

//hacia la primera posición.

Result:=pMin;

end;

http://www.aves.edu.co/ovaunicor/recursos/1/index_Metodos_ordenamiento.pdf

Ordenación por inserción

Este método de ordenación va considerando cada vez un subarray ordenado e inserta en él un nuevo elemento en su posición final. Inicialmente se considera el subarray que contiene únicamente el primer elemento del array. A este subarray se le van añadiendo iterativamente elementos para obtener subarrays ordenados cada vez más grandes. Este proceso se repite hasta que todos los elementos hayan sido insertados.

FOR Indice:= ExtremoIzqdo+1 TO ExtremoDcho DO

BEGIN

ElementoConsiderado:= Vector[Indice];

{ Insertar ElementoConsiderado en la posición adecuada dentro del subarray ExtremoIzqdo..Indice-1 }

END;

Para encontrar la posición del subarray ordenado en la que el ElementoConsiderado debe insertarse, éste se va comparando cada vez con un elemento del subarray ordenado tomándolos de derecha a izquierda. Si no es la posición adecuada, el elemento del subarray se desplaza a su derecha, con lo que cede su posición por si el ElementoConsiderado debiese situarse en ella. Si se trata de la posición adecuada, el ElementoConsiderado se sitúa en ella. Este proceso de comparación y desplazamiento debe terminar cuando se localiza la posición adecuada o bien cuando se alcanza la primera posición del array, lo que ocurrirá si el ElementoConsiderado es menor que todos los elementos del subarray ordenado.

FOR Indice:= Extremolzgdo+1 TO ExtremoDcho DO

BEGIN

ElementoConsiderado:= Vector[Indice];

Posicion:= Indice-1;

...