UNIDAD 3: Tipos De Ordenacion

                         TIPOS DE ORDENACIÓN

ORDENACIÓN:

La ordenación o clasificación de datos (sort en inglés) es una operación consistente en disponer un conjunto estructura de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres. Los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor numérico del elemento.

ORDENACIÓN POR SELECCIÓN:

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:

· Buscar el mínimo elemento de la lista
· Intercambiarlo con el primero
· Buscar el siguiente mínimo en el resto de la lista
· Intercambiarlo con el segundo

Y en general:

· Buscar el mínimo elemento entre una posición i y el final de la lista
· Intercambiar el mínimo con el elemento de la posición i

De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

 

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar () sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar () que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar (lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).

Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.

ORDENACIÓN POR INTERCAMBIO:

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Éste algoritmo es esencialmente un algoritmo de fuerza bruta lógica.

„Este método es clásico y muy sencillo, aunque por desgracia poco eficiente. La ordenación por burbuja (<<buble sort») se basa en comparar elementos adyacentes de la lista (vec- tor) e intercambiar sus valores si están desordenados. De este modo se dice que los valo- res más pequeños burbujean hacia la parte superior de la lista (hacia el primer elemen- to), mientras que los valores más grandes se hunden hacia el fondo de la lista. Consideremos, como ya se ha expuesto, clasificaciones en orden creciente

ORDENACION POR INSERCIÓN:

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²)operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

for (i=1; i<TAM; i++)

   temp = lista[i];

   j = i - 1;

   while ( (lista[j] > temp) && (j >= 0) )

   lista[j+1] = lista[j];

   j--;

   lista[j+1] = temp;

ORDENACIÓN POR DISTRIBUCIÓN:

Los algoritmos de ordenamiento externo, se basan en el principio de intercalación, sin embargo existen otras formas de ordenamiento con cintas. Una de estas formas se basa precisamente en el principio de ordenamiento por distribución radix.
Para aplicar esta idea a un ordenamiento externo, se debe tomar en cuenta que se deben tener tantas cintas como símbolos diferentes para ordenar y colocar las llaves en la cinta correspondiente en cada pasada, de acuerdo a:
* En T0 si el dígito es 0; en T1 si el dígito es 1; En T2 si el dígito es 2; etc.
Es importante recordar que los dígitos se toman a partir del menos significativo.
Ejemplo:
Para mostrar el funcionamiento de este método consideremos el siguiente conjunto de datos que solamente involucra a los dígitos: 0, 1, 2, y 3: {1023, 0122, 1131, 3123, 0012, 0132, 2013, 1110}.
* En la primera pasada las cintas quedan:
• T0: {1110}; T1: {1131}; T2: {0122, 0012, 0132} y T3: {1023, 3123, 2013}.
} En la segunda pasada:
• T0: {}; T1: {1110, 0012, 2013}; T2: {0122, 1023, 3123} y T3: {1131, 0132}.
* Y así

Agrupamos elementos, clasificándolos de acuerdo a cierto criterio y acorde a su naturaleza; es decir,
podemos agrupar números; letras, etc, etc. pero si te fijas en cada agrupación o montón, podemos "ordenar" por su jerarquía cada elemento.

Si fueran números enteros: 899, 3, 67, 98, 1.... Este grupo podemos ordenarlo 1, 3, 67, 899..

Si fueran letras: x, b, r, o.... las ordenamos b, o, r, x ....

Ejemplos bastante claros de ordenar palabras por distribución sería "un diccionario" cada registro de una "base de datos", etc, etc.

1.- Definir un arreglo en el que cada posición puede ser ocupada por más de un registro (un arreglo de arreglo  de registros) puede darse la situación de ser insuficiente la cantidad de registros adicionales o de existir demasiado desperdicio de memoria.

2.- Definir el tamaño de la urna variable a través del uso de estructuras como las listas simples enlazadas

n= Elementos del vector a ordenar
b= vector destino
a= vector origen                                                               

for( i=0 ; i < 8 ; i++ )
{
    b[ a[i] ]=a[i];
}

ORDENACIÓN POR INTERCALACIÓN:

Intercalación Simple:

El método de ordenación por intercalación es utilizado por los jugadores de cartas o naipes para ordenar sus barajas. Consiste en mirar las cartas una a una y cuando se ve cada nueva carta se inserta en el lugar adecuado. Para desarrollar el algoritmo imaginemos que las cartas se encuentran situadas en una fila encima del tapete; a medida que se ve una carta nueva, ésta se compara con la fila y se debe empujar alguna de ellas a la derecha para dejar espacio e insertar la nueva.

Consideremos un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementando en 1, el elemento del subíndice del vector se elimina de la secuencia y se reinserta en el vector en la posición adecuada.

Algoritmo

n=tamaño del vector
int i,k,aux;
boolean band=false;
for (k=1;k < n; k++){
    aux=vect[k];
    i=k-1;
    band=false;
    while( i>=0 && !band ){
        if(aux < vect[i]){
            vect[i+1]=vect[i];
            i--;
        }
        else{
            band=true;
        }
    }
    vect[i+1]=aux;
}

Intercalación Binaria:

El algoritmo de ordenación por intercalación simple requiere una exploración o búsqueda secuencial para localizar la posición de un elemento en la sublsta ordenada. Si en lugar de considerar una búsqueda secuencial se realizara una búsqueda binaria se mejoraría considerablemente el algoritmo y se aumentaría la velocidad de ejecución. Esta modificación se conoce como método de intercalación binaria.
Este algoritmo utiliza la técnica de dividir y conquistar por lo tanto, divide el vector y toma un elemento pivote y compara contra él los elementos del vector dividido.

Algoritmo:

n=tamaño del vector
int i,j,izq,der,m,aux;
for(i=1; i < n; i++){
    aux=vect[i];
    izq=0;
    der=i-1;
    while( izq<=der ){
        m=(izq+der)/2;
        if(aux<=vect[m])
            der=m-1;
         else
            izq=m+1;
    }
    j=i-1;
    while(j>=izq){
        vect[j+1]=vect[j];
        j--;
    }
    vect[izq]=aux;
}

Intercalación Merge

Cuando se dispone de dos vectores ya ordenados y se desea obtener un tercer vector también ordenado, se puede realizar la ordenación con un método denominado Mezcla (Merge en ingles). Supongamos que A es un vector ordenado de m elementos y B es otro vector ordenado de n elementos. La operación de mezcla producirá un nuevo vector de m + n elementos.

El método más sencillo, pero menos eficaz, consiste en colocar una lista detrás de la otra y luego ordenarla. Sin embargo este método no aprovecha la propiedad de que los vectores A y B ya están ordenados, por ello debe recurrir normalmente al sistema de mezcla el cual cosiste en comparar los dos primeros elementos de los vectores (A y B) y enviar al menor al tercer vector, continuando con el elemento comparado pero no enviado con el siguiente elemento del vector que contiene al elemento menor comparado anteriormente y así sucesivamente. Una vez que se terminaron los elementos de un vector, se procede a vaciar los elementos restantes del otro vector.

Algoritmo:

m=tamaño del vector1
n=tamaño del vector2
int m,n,i=0,j=0,k=0,p;
while( i < m && j < n ){
    if( vec1[i] <= vec2[j] ){
        mezcla[k]=vec1[i];
        i++;
    }
    else{
        mezcla[k]=vec2[j];
        j++;
    }
    k++;
}
if( i>= m){
    for( p=j; p < n; p++){
        mezcla[k]=vec2[p];
        k++;
    }
}
if( j>=n ){
    for( p=i; p < m; p++ ){
        mezcla[k]=vec1[p];
        k++;
    }
}

ORDENACIÓN POR POLIFASE:

La idea básica tras este método es aplicar una estrategia mezclar hasta vaciar el archivo, utilizando archivos auxiliares para almacenar el resultado parcial. Durante la ejecución, el archivo de entrada y alguno de salida intercambian papeles y siempre se tiene alguno vacío. El algoritmo es el siguiente:
* Fase 1, mientras existan datos en T0 (entrada), los pasos a seguir son:
1. Leer m llaves
2. Ordenar las llaves por método interno.
3. Si las m llaves anteriores se colocaron en T2 colocar éstas en T3, si no, colocarlas en T2.
* Fase 2, mientras exista más de un arreglo, los pasos a seguir son:
1. Intercalar el primer bloque en T2 con el primer bloque en T3 y dejar el resultado en T0.
2. Intercalar los siguientes arreglos en T2 y T3 y dejar el resultado en T1.
3. Repetir los pasos 1. y 2. colocando los resultados alternativamente en T0 y T1 hasta que los datos en T2 y T3 se agoten.

ORDENACIÓN POR CASCADA:

En este caso la distribución de las llaves en cada uno de los archivos auxiliares, sigue una secuencia que involucra a los números de Fibonacci. La distribución se hace sobre 6 archivos auxiliares T0, T1, T2, T3, T4 y T5.

* Fase 1, mientras existan registros en T5 los pasos a seguir son:
1. Leer m llaves.
2. Ordenar las m llaves por un método interno.
3. Distribuir en las cintas usando una secuencia de Fibonacci.
* Fase 2, mientras exista más de un arreglo en alguna cinta, los pasos a seguir son:
1. Intercalar el primer arreglo de los archivos, T0, T1, T2, T3, T4 en T5 hasta agotar T4, intercalar T0, T1, T2, T3 en T4 hasta agotar T3, etc. Finalmente copiar T0 a T1.
2. Intercalar T1, T2, T3, T4, T5 en T0 Hasta agotar T1, intercalar T2, T3, T4, T5 en T1 hasta agotar T2, etc. Finalmente intercalar T4, T5 en T3 hasta agotar T4, por último copiar T5 a T4.

ORDENACION POR OSCILANTES

En los dos métodos de ordenamiento externo anteriores, existen 2 fases claras en sus algoritmos: distribución e intercalación; con una característica común: nunca se pasa a la segunda fase hasta no haber completado la primera. En el método oscilante, en el ordenamiento se propone un algoritmo que combina distribución  mezcla de los arreglos, de tal manera que gran parte del proceso de ordenamiento toma lugar antes de que la entrada sea completamente examinada. Considerando que la distribución y mezcla de los arreglos se realiza sobre cinco archivos auxiliares: T0, T1, T2, T3, T4; el algoritmo es el siguiente:
* Hacer las fases 1 y 2 alternadamente hasta que la entrada se agote:
* Fase 1, para i = 1 a 4.
1. Leer m llaves.
2. Ordenar las m llaves con un método interno.
3. Distribuir los arreglos (para la primera pasada se acomodan en T0, T1, T2, T3, dejando
T4 para el resultado, en la segunda pasada se acomoda en T1, T2, T3, T4, en la tercer pasada en T0, T2, T3, T4, etc.)
* Fase 2
• Intercalar para la primera pasada los arreglos T0, T1, T2, T3 en T4, el arreglo en T4 tiene orden decreciente.
• Para la siguiente pasada intercalar los arreglos de T1, T2, T3, T4, en T0 el que también tiene orden decreciente, etc.
• El proceso continúa hasta acomodar en las cintas solamente arreglos en orden decreciente, los que formarán un archivo final ascendente durante un proceso de intercalación.