Métodos De Ordenamiento De Un Vector

Los métodos de ordenamiento son necesarios para que luego de ordenar, se puedan buscar datos de una manera mucho mas rápida y eficiente aplicando distintas técnicas.

MÉTODO DE ORDENAMIENTO POR BURBUJA

Definición

La idea de este método es ir tomando los elementos de a dos e ir comparándolos e intercambiándolos de ser necesario, hasta que todos los elementos sean comparados.

Diagrama de flujo

Algoritmo

for (i=0; i<n-1; i++) {       for (j=i+1; j<n; j++)      {        if(V[i]>V[j])     {        aux = V[i];        V[i] = V[j];        V[j] = aux;      }    } }

Ventajas	Desventajas
A) Fácil implementación	A) Muy lento
B) No requiere memoria adicional.	B) Realiza numerosas comparaciones
C) Realiza numerosos intercambios.

Ejemplo

MÉTODO DE ORDENAMIENTO POR INSERCIÓN

En este procedimiento se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte de arriba del arreglo, que ya se encuentra ordenado. El proceso, al igual que en el método de inserción directa, se repite desde el segundo hasta el n-enésimo elemento.

Algoritmo

for(i=1; i<n; i++) {   temp = V[i];   Izq = 0;   Der = i-1;   while(Izq <= Der){     Medio = (Izq+Der)/2;     if (temp < V[Medio])       Der = Medio - 1;     else       Izq = Medio + 1;   }   for (j=i-1; j>=Izq; j--){     V[j+1]=V[j];   }   V[Izq] = temp; }

Diagrama De Flujo

Ventajas Desventajas A) Fácil implementación.                        A) Lento. B) No requiere memoria adicional. B) En promedio hace numerosas comparaciones.

MÉTODO DE ORDENAMIENTO POR SELECCIÓN. Entre los métodos elementales de ordenación de vectores se encuentra el algoritmo de selección: Algoritmo for (i=0; i<n; i++) {    imin=i;    for (j=i+1; j<n; j++)   {     if(V[j]<V[imin])     imin=j;   }   aux = V[i];   V[i] = V[imin];   V[imin] = aux; } Es decir, el método se basa en buscar en cada iteracción el mínimo elemento del “subvector” situado entre el índice i y el final del vector e intercambiarlo con el de índice i. Tomando la dimensión del vector n como tamaño del problema es inmediato que el bucle se repite n veces y por tanto la función que da el número de repeticiones es de tipo lineal. Diagrama de flujo Análisis del algoritmo. Estabilidad: No es estable. Intercambia registros con claves iguales. Requerimientos de Memoria: Este algoritmo sólo requiere de una variable adicional para realizar los intercambios sin importar qué tan grande sea el vector. Requerimiento constante. Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad promedio es también O(n2). Ventajas Desventajas A) Fácil implementación A) Lento B) No requiere memoria adicional. B) Realiza numerosas comparaciones. C) Realiza pocos intercambios. C) Este es un algoritmo lento No obstante, ya que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas. MÉTODO DE ORDENAMIENTO POR SHELL Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del Bubble Sort, sin embargo no ordena elementos adyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande (pero menor al tamaño total de la estructura) y van disminuyendo hasta llegar al '1'. Este método funciona de la siguiente manera: Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1. "Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos." Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1. Algoritmo: void shellSort(int a[], int h) {   int i;   while (h > 0)   { for (i = h-1; i<n; i++)     {        int B = a[i];        int j = i;        for (j = i; (j >= h) && (a[j - h] > B); j -= h)        { a[j] = a[j - h];}          a[j] = B;      }        h = h / 2;   } } Análisis del algoritmo. Estabilidad: Este algoritmo se considera estable. Requerimientos de Memoria: Una variable adicional para realizar los intercambios. Y una variable para el salto. Requerimiento constante. Tiempo de Ejecución: Los estudios realizados indican que su complejidad es de O(n^1.2) en el mejor caso y de O(n^1.25) en el caso promedio. QUICKSORT La ordenación rápida, inventada y nombrada por C.A.R. Hoare en 1960, está considerada como el mejor algoritmo de ordenación disponible actualmente. Está basada en la ordenación por el método de intercambio. La ordenación rápida se basa en la idea de las particiones. El procedimiento general es seleccionar un valor llamado COMPARANDO y entonces dividir el array en dos partes. En un lado todos los elementos mayores o iguales al valor de partición y en otro todos los elementos menores que el valor. Este proceso se repite en cada parte restante hasta que el array esté ordenado. Como se puede ver, este proceso es esencialmente recursivo por naturaleza y, de hecho, las implementaciones más claras de la ordenación rápida es por algoritmos recursivos. La selección del valor comparado se puede obtener de dos formas. Se puede seleccionar aleatoriamente o haciendo la media de un pequeño conjunto de valores tomados del array. Para una ordenación óptima es mejor seleccionar un valor que este precisamente en medio del rango de valores. Sin embargo, esto no es fácil de hacer en la mayoría de los conjuntos de datos. En el caso peor, el valor escogido está en un extremo. Incluso en este, la ordenación rápida todavía funciona bien. La versión de la ordenación rápida que sigue selecciona el elemento mitad del array. Aunque no siempre será una buena elección, la ordenación sigue funcionando correctamente. Diagrama de flujo Algoritmo: void ordenar (int vect[], int ind_izq, int ind_der) {   int i, j; /* variables indice del vector */   int elem; /* contiene un elemento del vector */   i = ind_izq;   j = ind_der;   elem = vect[(ind_izq+ind_der)/2];   do   {while (vect[i] < elem) //recorrido del vector hacia la derecha     i++;    while (elem < vect[j]) // recorrido del vector hacia la izquierda     j--;    if (i <= j) /* intercambiar */    { int aux; /* variable auxiliar */      aux = vect[i];      vect[i] = vect[j];      vect[j] = aux;      i++;      j--;    }   } while (i <= j);   if (ind_izq < j) {ordenar (vect, ind_izq, j);} //Llamadas recursivas   if (i < ind_der) {ordenar (vect, i, ind_der);} } Análisis del algoritmo. Estabilidad: No es estable. Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. Tiempo de Ejecución: Caso promedio. La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como: f(1) = 1 f(n) = n + 2 f(n/2) La forma cerrada de esta expresión es: f(n) = n log2n Es decir, la complejidad es O(n log2n). El peor caso ocurre cuando la lista ya está ordenada, porque cada llamada genera sólo una sublista (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n2). Con las optimizaciones mencionadas arriba puede evitarse este comportamiento. Ventajas Desventajas A) Generalmente es el más rápido                                    A) Implementación un poco más complicada B) No requiere memoria adicional B) Mucha diferencia entre el peor (n2) y el mejor caso (log n) C) Intercambia registros iguales RESUMEN DE LOS MÉTODOS Tabla comparativa de algoritmos Nombre Complejidad Estabilidad Memoria adicional Burbuja O(n2) SI         NO Selección O(n2) NO     NO Inserción O(n2) SI     NO Shell O(n1.25) SI     NO Rápido (Quicksort) O(n * log(n)) NO     NO Autor: Wilmer Morales 633