Calculo Vectorial

5.1. Método de burbuja

Método de Burbuja.

El método de burbuja también se le puede llamar como Método de "intercambio directo". El algoritmo ordena los elementos del arreglo utilizando el método de la burbuja . Transporta en cada pasada el elemento más pequeño hacia la parte de izquierda del arreglo.

Este ordenamiento es eficiente sólo en listas pequeñas (10 elementos).

El método de burbuja va comparando cada elemento del arreglo con el siguiente; si un elemento es mayor que el que le sigue, entonces se intercambian; ésto producirá que en el arreglo quede como su ultimo elemento, el más grande. Este proceso deberá repetirse recorriendo todo el arreglo hasta que no ocurra ningun intercambio. Los elementos que van quedando ordenados ya no se comparan. "Baja el más pesado".

Este método se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.

A continuación se muestra el código de el método de la burbuja

método de ordenamiento burbuja

public void burbuja ()

{inicio del método burbuja

for(int i=nElementos-1;i>1;i--)primer

for recorre

el arreglo

{

for(int j=1;j<=i;j++)for interno compara

{

if (datos[j-1]>datos[j])

intercambiar(j-i,j);

}fin del for interno

}fin del primer for recorre

}//fin del método burbuja

5.1.2. Método Quicksort

MÉTODO DE ORDENACIÓN DE QUICKSORT

El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo.

Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.

Este tipo de algoritmos se basa en la técnica "divide y vencerás", o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños , que un arreglo o lista grande.

Normalmente al inicio de la ordenación se escoge un elemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo.

Se podrá garantizar que los elementos a la izquierda de la mitad son los menores y los elementos a la derecha son los mayores.

Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación por partición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad.

Así se continúa hasta que el tamaño de los arreglos a ordenar es 1, es decir, todos los elementos ya están ordenados.

En promedio para todos los elementos de entrada de tamaño n, el método hace O(n log n) comparaciones, el cual es relativamente eficiente.

Algoritmo (Orientado a C)

void ordena( int vect[], int izq, int der ){

int i = 0, j = 0;

int x = 0, aux = 0;

i = izq;

j = der;

x = vect [ (izq + der) /2 ];

do{

while( (vect[i] < x) && (j <= der) ){

i++;}

while( (x < vect[j]) && (j > izq) ){

j--;}

if( i <= j ){

aux = vect[i];

vect[i] = vect[j];

vect[j] = aux;

i++; j--;

}

}while( i <= j );

if( izq < j )

ordena( vect, izq, j );

if( i < der )

ordena( vect, i, der );

}

QUICKSORT

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

La idea central de este algoritmo consiste en los siguiente:

Se toma un elemento x de una posición cualquiera del arreglo.

Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.

Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Ejemplo: A: 15,67,08,16,44,27,12,35

Se selecciona A[i] x=15

Primera pasada (DER-IZQ)

A[8] >= x 35 >= 15 No hay intercambio

A[7] >= x 12 >= 15 Si hay intercambio

A: 12,67,08,16,44,27,15,35

(IZQ-DER)

A[2] < = X 67 < = 15 Si hay intercambio

A:12,15,08,16,44,27,67,35

2da. Pasada (DER-IZQ)

A[6] >= x 27 >= 15 No hay intercambio

A[5] >= x 44 >= 15 No hay intercambio

A[4] >= x 16 >= 15 No hay intercambio

A[3] >= x 08 >= 15 Si hay intercambio

A: 12,08,15,16,44,27,67,35

Como el recorrido de izquierda a derecha debería iniciarse en la misma posición donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se encuentra en la posición correcta.

A: 12, 08, 15, 16, 44, 27, 67, 35

1er 2do Conjunto

Conjunto

16, 44, 27, 67, 35 x16

(DER-IZQ)

A[8]>=x No hay intercambio

A[7]>=x No hay intercambio

A[6]>=x No hay intercambio

A[5]>=x No hay intercambio

A: 12, 08, 15, 16, 44, 27, 67, 35 xß44

(DER-IZQ)

A[8]>= x Si hay intercambio

A: 12, 08, 15, 16, 35, 27, 67, 44

(IZQ-DER)

A[6] < = x No hay intercambio

A[7] < = x Si hay intercambio

12, 08, 15, 16, 35, 27, 44, 67 12, 08, 15, 16, 35, 27, 44, 67 35, 27, 44, 67 xß35

(DER-IZQ)

A[8] >= x No hay intercambio

A[7] >= x No hay intercambio

A[6] >= x Si hay intercambio

12, 08, 15, 16, 27, 35, 44, 67 12,08 xß12

(DER-IZQ)

A[2]>=x Si hay intercambio

EL VECTOR ORDENADO: 08,12,15,16,27,35,44,67

ANÁLISIS DE EFICIENCIA DEL MÉTODO DE QUICKSORT

Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n. Respecto al número de comparaciones,

...