Definición de metodos de ordenación

Fuente:http://www.ica.luz.ve/juancol/eda/ordenacion/ordenacion.html

Los métodos de ordenación elementales proporcionan:

-Una terminología básica
-Un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño.

Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.

Como regla general se tiene que los métodos elementales necesitan cerca de pasos para ordenar elementos organizados al azar.

En general, no se recomienda su uso para ordenar:

-Archivos grandes
-Archivos clasificados aleatoriamente.

Por su parte, métodos mas avanzados pueden lograr desempeños de orden , , . Mas aún, se puede demostrar que ningún método de ordenación puede utilizar menos de comparaciones entre claves cuando éstas están organizadas al azar.

Terminología General

En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.

Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargado en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques.

Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria.

Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.

Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.

Que es el Intercambio Directo?
Ordenación por intercambio

Fuente: http://www.geocities.com/j_santanah/intercambio.htm

Ordenación por intercambio Directo (burbuja).- La idea básica de este algoritmo consiste en compara pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

Ejemplos: Suponga 16, 67, 08, 16, 44, 27, 12, 35

Primera pasada
A[7] > A[8] 12>35 No hay intercambio
A[6] > A[7] 27>12 Si hay intercambio
A[5] > A[6] 44>12 Si hay intercambio
A[4] > A[5] 16>12 Si hay intercambio
A[3] > A[4] 08>12 No hay intercambio
A[2] > A[3] 67>08 Si hay intercambio
A[1] > A[2] 15>08 Si hay intercambio

Luego de la primera pasada
A: 08, 15, 67, 12, 16, 44, 27, 35

Luego de la segunda pasada
A:= 08, 12, 15, 67, 16, 27, 44, 35
3ª. Pasada 08, 12, 15, 16, 67, 27, 35, 44
4ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
5ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
6ª. Psada 08, 12, 15, 16, 27, 35, 67, 44
7ª. Pasada 08, 12, 15, 16, 27, 35, 44, 67

BURBUJA1(A,N)

El algoritmo ordena los elementos del arreglo utilizando el método de burbuja, transporta en cada pasada el elemento más pequeño hacia la parte izquierda del arreglo. A es un arreglo de N elementos. {I, J, aux son variables de tipo entero}

1.- Repetir con I desde 2 hasta N
1.1.- Repetir con J desde N hasta I
1.1.1.- Si A[J-1]>A[J] entonces hacer: aux<- a[J-1], a[J-1]<- A[J] A[J]<-aux
1.1.2.- {fin del condicional del paso 1.1.1
1.2.- {in del ciclo del paso
1.12.- {fin del ciclo de paso1

ANALISIS DE EFICIENCIA DEL METODO DE INTERCAMBIO DIRECTO (BURBUJA)

El número de comparaciones en el método de la burbuja es fácilmente contabilizable. En la primera pasada realizamos (n-1) comparaciones, en la segunda pasada (n-2) comparaciones, en la tercera pasada (n-3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo.

Por lo tanto:
C=(n-1)+(n-2)+.......................+2+1= n*(n-1)/2
Que es igual a: C = (n2-n)/2

Respecto al número de movimientos, estos dependen de si el arreglo está ordenado desordenado o en orden inverso.

Los movimientos para cada uno de los casos son:
Mmin = 0
Mmed = 0.75*(n2-n)
Mmax = 1.5*(n2-n)

El tiempo necesario para ejecutar el algoritmo de burbuja es proporcionar a n2, o(n2) donde n es el número de elementos del arreglo.