Monografía Sobre Metodos De Ordenamiento Y Analisis De Algoritmos 3a6a59

MONOGRAFÍA SOBRE METODOS DE ORDENAMIENTO Y ANALISIS DE ALGORITMOS

Alonso Olivera Juan José Francisco

1K7

¿Qué es el Análisis Algorítmico? El análisis algorítmico es la actividad dedicada a determinar la cantidad de recursos (memoria y tiempo) que consumen los algoritmos para resolver un problema computacional dado. Es una disciplina de las Ciencias de la Computación. Cuando para resolver dicho problema hay varios algoritmos, hay que optar entre ellos de acuerdo a cuál es el que mejor se adecua a nuestros intereses. Como en la mayoría de los casos la elección de un buen algoritmo está orientada hacia la disminución del costo que implica la solución del problema, se tiende a elegir el algoritmo de acuerdo a dos clases de criterios: a) Criterios orientados a minimizar el costo de desarrollo: claridad, sencillez y facilidad de implantación, depuración y mantenimiento. b) Criterios orientados a disminuir el costo de ejecución: tiempo de procesador y cantidad de memoria utilizados.

Orden de un Algoritmo Ordenar, en los procesamientos de datos, es el proceso de reorganizar un conjunto de datos de objetos en una secuencia determinada, con el objetivo de facilitar la búsqueda de uno o más elementos pertenecientes al conjunto. Ordenar es colocar información de una manera particular basada en un criterio de ordenamiento. Un algoritmo de ordenamiento es un algoritmo que pone datos de un conjunto en una secuencia dada por una relación de orden. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico (Es conocido principalmente por su aplicación a cadenas de caracteres, por ejemplo en diccionarios o en la guía telefónica.). Los ordenamientos eficientes son importantes porque optimizan el uso de otros algoritmos (como los de búsqueda y

fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

Métodos de ordenamiento

Intercambio o burbuja mejorado (Iterativo) 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 un método comparativo. El algoritmo resultante, para ordenar una lista de menor a mayor, partiendo del hecho de que los datos a ordenar están en una lista de N elementos es el siguiente: 1) Comparamos el primero con el segundo, este con el tercero, este con el cuarto, etc. Cuando el resultado de una comparación sea “mayor que” se intercambian los valores de los elementos comparados. Con esto se consigue llevar el valor mayor a la posición n. 2) Repetimos lo ya hecho, pero ahora para los N-1 primeros elementos de la lista, y así sucesivamente. 3) Repetimos nuevamente lo ya hecho, pero ahora para los N-2 primeros elementos de la lista, y así sucesivamente. 4) El proceso termina después de repetir el punto 1, N-1 veces, o cuando al finalizar la ejecución del punto 1 no haya habido ningún cambio (variable bandera). main (void) { tipovec VEC; int L,N,I; float AUX; bool B; leervec(N,VEC); L=N-1; do { B=false; for (I=0;I VEC[I+1]) {AUX=VEC[I]; VEC[I]= VEC[I+1]; VEC[I+1]=AUX;

}

L=L-1;} while (B);

B=true;}

Inserción o método de la baraja (Iterativo) Se le llama método de la baraja porque puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Se ordenan los dos primeros elementos del array y luego se inserta el tercer elemento en la posición correcta con respecto a los tres elementos ya clasificados y así sucesivamente hasta llegar al último elemento del array. main (void) { tipovec VEC; int I,N,K; leervec(N,VEC); I=2; while (I<=N) { VEC[0]=VEC[I]; K=I-1; while (VEC[0]
Selección o método sencillo (Iterativo) Este algoritmo mejora ligeramente el algoritmo de la burbuja. Su funcionamiento es el siguiente:  Buscar el mínimo elemento de la lista  Intercambiarlo con el primero

 Buscar el 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 main (void) { tipovec VEC; int I,N,P,K; float AUX; leervec(N,VEC); for (I=0;I
Rápido o QuickSort (recursivo) Está basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Es probablemente la técnica más rápida conocida. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento. El algoritmo trabaja de la siguiente forma: 1) Se elige un elemento cualquiera de la lista de elementos a ordenar, al que llamaremos elemento de división. 2) Buscar la posición que le corresponde en la lista ordenada. 3) Resituar los demás elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

4) La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del elemento de división, y otra por los elementos a su derecha. 5) Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

void quicksort(int A[],int izq, int der ) { int i, j, x , aux; i = izq; j = der; x = A[ (izq + der) /2 ]; do { while( (A[i] < x) && (j <= der) ) {i++;} while( (x < A[j]) && (j rel="nofollow"> izq) ) { j--;} if( i <= j ) { aux = A[i]; A[i] = A[j]; A[j] = aux;i++; j--; } }while( i <= j ); if( izq < j ) quicksort( A, izq, j ); if( i < der ) quicksort( A, i, der ); }

Por Mezcla o MergeSort (recursivo) El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

 Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.  Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera: 

Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:  Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.  Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.  Mezclar las dos sublistas en una sola lista ordenada . #include <stdlib.h> #include <stdio.h> void mergesort(int *v, int i, int f); void merge(int *v, int i, int m, int f); int main() { int *v, n; printf("Ingrese N: "); scanf("%d", &n); v = new int[n]; for(int i=0; i
return 0;

void mergesort(int *v, int i, int f) { if(i!=f) { int m = (i+f)/2; mergesort(v, i, m);

mergesort(v, m+1, f); merge(v, i, m, f); }

}

void merge(int *v, int i, int m, int f) { int *aux = new int[m-i+1]; for(int j=i; j<=m; j++) aux[j-i] = v[j]; int c1=0, c2=m+1; for(int j=i; j<=f; j++) { if(aux[c1] < v[c2]) { v[j] = aux[c1++]; if(c1==m-i+1) for(int k=c2; v[++j] = } else { v[j] = v[c2++]; if(c2==f+1) for(int k=c1; v[++j] = } }

k<=f; k++) v[k];

k<=m-i; k++) aux[k];

}

Caso mejor Intercambio o burbuja mejorado Inserción o método de la baraja

Selección o método sencillo Rápido o QuickSort

Caso peor

Caso promedio 2 Su tiempo de ejecución es O(N ) para el mejor, peor y caso promedio.

Si la entrada O (N2) se El caso esta "casi cumple cuando promedio es O ordenada", el la entrada está (N2). algoritmo se totalmente ejecuta mucho ordenada. más rápidamente. Esta velocidad tiende a un tiempo O(N). Su tiempo de ejecución es O(N2) para el mejor, peor y caso promedio. En el mejor caso, el elemento de división termina en el

En el peor caso, el elemento de división termina en un

En el caso promedio, el orden es O(n log n).

Por Mezcla o MergeSort

centro de la extremo de la lista, lista. El orden dividiéndola en de complejidad dos sublistas del algoritmo de igual es entonces de tamaño. En O (n²). este caso, el orden de complejidad del algoritmo es O(n log n). El tiempo de ejecución promedio es O(N log(N)).

Caso mejor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una menor complejidad computacional. Caso peor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una complejidad computacional mayor. Caso promedio: la situación inicial de los datos no sigue ningún patrón preestablecido que aporte ventajas o desventajas. Se puede considerar, por tanto, la situación típica de ejecución del algoritmo.

Comparación en el caso promedio entre los métodos BURBUJA-INSERCIÓN-SELECCIÓN y el método QUICKSORT-MERGESORT