ANALISIS ALGORITMOS ORDENACION

  • View
    10

  • Download
    0

Embed Size (px)

Text of ANALISIS ALGORITMOS ORDENACION

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    1/17

    Anlisis de la complejidad

    computacional de losalgoritmos de ordenacin

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    2/17

    INSERCION

    Insercion(int matrix[]){

    int i, temp, j;for (i = 1; i < matrix.length; i++){

    temp = matrix[i];

    j = i - 1;while ( (matrix[j] > temp) && (j >= 0) ){

    matrix[j + 1] = matrix[j];j--;

    }matrix[j + 1] = temp;}

    }

    EN LA CLASE: ANALIZA EL TIEMPO DE EJECUCIN _ COMPLEJIDAD

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    3/17

    SELECCION

    Seleccion(int[]matrix)

    {int i, j, k, p, buffer, limit = matrix.length-1;for(k = 0; k < limit; k++){

    p = k;

    for(i = k+1; i

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    4/17

    Algoritmo quicksor t

    La primera etapa en el algoritmo de particin es obtenerel elemento pivote;

    Una vez que se ha seleccionado se ha de buscar el

    sistema para situar en la sublista izquierda todos loselementos menores que el pivote y en la sublistaderecha todos los elementos mayores que el pivote.

    Supongamos que todos los elementos de la lista sondistintos, aunque ser preciso tener en cuenta los casosen que existan elementos idnticos

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    5/17

    El primer problema a resolver en el diseo del algoritmode quicksort es seleccionar el pivote.

    Aunque la posicin del pivote, en principio, puede sercualquiera, una de las decisiones ms ponderadas es

    aquella que considera el pivote como el elemento centralo prximo al central de la lista

    Veamos el siguiente ejemplo

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    6/17

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    7/17

    Los pasos que sigue el algoritmo quicksort:

    Seleccionar el elemento central de a[0:n-1] como pivote

    Dividir los elementos restantes en particiones izquierda y derecha,de modo que ningn elemento de la izquierda tenga una clave(valor) mayor que el pivote y que ningn elemento a la derecha

    tenga una clave ms pequea que la del pivote.

    Ordenar la particin izquierda utilizando quicksort recursivamente.

    Ordenar la particin derecha utilizando quicksort recursivamente.

    La solucin es particin izquierda seguida por el pivote y acontinuacin particin derecha.

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    8/17

    Codificacin en C del algoritmo quicksor tvoid quicksort(double a[], int primero, int ultimo){

    int i, j, central;double pivote;

    central = (primero + ultimo)/2;pivote = a[central];i = primero;

    j = ultimo;do {

    while (a[i] < pivote) i++;while (a[j] > pivote) j--;if (i

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    9/17

    Anlisis del algoritmo quicksor t

    El anlisis general de la eficiencia de quicksort es difcil. La mejor forma deilustrar y calcular la complejidad del algoritmo es considerar el nmero de

    comparaciones realizadas teniendo en cuenta circunstancias ideales.Supongamos que n (nmero de elementos de la lista) es una potencia de 2,n = 2k(k = log2n).

    Adems, supongamos que el pivote es el elemento central de cada lista, demodo que quicksort divide la sublista en dos sublistas aproximadamente

    iguales.

    En la primera exploracin o recorrido hay n 1 comparaciones. El resultado dela etapa crea dos sublistas aproximadamente de tamao n/2.

    En la siguiente fase, el proceso de cada sublista requiere aproximadamente n/2comparaciones. Las comparaciones totales de esta fase son 2(n/2) = n.

    La siguiente fase procesa cuatro sublistas que requieren un total de 4(n/4)comparaciones, etc.

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    10/17

    Eventualmente, el proceso de divisin termina despus de k pasadascuando la sublista resultante tenga tamao 1.

    El nmero total de comparaciones es aproximadamente:

    n + 2(n/2) + 4(n/4) + + n(n/n) = n + n + + n = n k = n log2 n

    Para una lista normal la complejidad de quicksort es O(n log2n)

    El caso ideal que se ha examinado se realiza realmente cuando la lista(el array) est ordenado en orden ascendente. En este caso elpivote es precisamente el centro de cada sublista.

    Si el array est en orden ascendente, el primer recorrido encuentra elpivote en el centro de la lista e intercambia cada elemento en lassublistas inferiores y superiores. La lista resultante est casiordenada y el algoritmo tiene la complejidad O(n log2n)

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    11/17

    El escenario del caso peor de quicksort ocurre cuando el pivote caeconsistentemente en una sublista de un elemento y deja el restode los elementos en la segunda sublista. Esto sucede cuando elpivote es siempre el elemento ms pequeo de su sublista.

    En el recorrido inicial, hay n comparaciones y la sublista grandecontiene n 1 elementos.

    En el siguiente recorrido, la sublista mayor requiere n 1

    comparaciones y produce una sublista de n 2 elementos, etc.

    El nmero total de comparaciones es:n + n 1 + n 2 + + 2 = (n 1)(n + 2)/2

    La complejidad es O(n2).

    En general el algoritmo de ordenacin tiene como complejidadmedia O(n log2n) siendo posiblemente el algoritmo ms rpido

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    12/17

    ORDENACIN POR MEZCLA

    En este caso se sigue un esquema similar a laordenacin rpida, el esquema de divide y vencers. Sinembargo el mayor esfuerzo no se realiza dividiendo elvector y reorganizando cada divisin, sino que tiene

    lugar cuando finalmente se construye el vector ordenadoa partir de la mezcla de los subvectores que se generan.

    La idea consiste en dividir el vector v en dos subvectores para posteriormente mezclar ordenadamente las

    soluciones obtenidas al ordenar A y B, aplicandonuevamente el algoritmo Merge Sort a ambossubvectores.

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    13/17

    PSEUDOCDIGO

    Si v es de tamao 1 entoncesel vector v ya est ordenado

    sinodividir v en dos subvectoresA y B

    fin {si}

    Ordenar A y B usando MergesortMezclar las ordenaciones de A y B para generar el vector ordenado.

    Donde dividir v en dos subvectores se puede refinar:

    Asignar a A el subvector[v1,.....,vnDIV2]Asignar a B el subvector[vnDIV2+1,......vn]

    Mientras que mezclar las ordenaciones de A y B consiste en ir

    entremezclando adecuadamente las componentes ya ordenadas de A y B.

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    14/17

    UN EJEMPLO

    V=[8,5,7,3]

    1. Mergedesdehasta(v,1,4)centro=21.1. Izq(1)

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    15/17

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    16/17

    CLCULO DE SU COMPLEJIDAD ALGORTMICA

    El peor caso: Puesto que la mezcla se ejecuta en un tiempo proporcional an (la longitud del vector a ordenar) el coste en tiempo vendr dado porla siguiente recurrencia:

    Esta ecuacin se resuelve mediante sustituciones sucesivas cuando n

    es una potencia de 2 (j tal que n=2j

    ).

    De donde sustituyendo jlog n lo que da una funcin de orden O(nlogn) (una vez aplicadas las reglas de la suma y de la escalabilidad)

  • 5/22/2018 ANALISIS ALGORITMOS ORDENACION

    17/17

    TAREA DE ENTRENAMIENTO

    REALIZAR EL ANALISIS DE TIEMPO DEEJECUCIONORDEN DE COMPLEJIDAD(PARA LOS CASOS PEOR, MEJOR, MEDIO)

    DE LOS ALGORITMOS: HEAPSORT YALGORITMOS DE BUSQUEDA:

    B. SECUENCIAL

    B. BINARIA ITERATIVA

    B. BINARIA RECURSIVA