Algoritmo de ordenamiento - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Jueves 28 de Marzo de 2024 |
 

Algoritmo de ordenamiento

Imprimir Recomendar a un amigo Recordarme el recurso

Un método un poco más rápido y simple de ordenar registros

Agregado: 03 de FEBRERO de 2005 (Por G. Javier Dillon Long) | Palabras: 737 | Votar |
1 voto | Promedio: 10
| Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Matemáticas >
Material educativo de Alipso relacionado con Algoritmo ordenamiento
  • Algoritmos y Estructuras de Datos I: Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales: Universidad de Buenos Aires Primer Cuatrimestre de 2000: Práctica 3 Primera Parte: Tipos Abstractos de Datos. Segunda Parte: Listas.
  • Algoritmos y Estructuras de Datos I: Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Primer Cuatrimestre de 2000. Resolución del Parcial 18.
  • Algoritmos y Estructuras de Datos I: Programación Imperativa: ...

  • Enlaces externos relacionados con Algoritmo ordenamiento


    Publicado por G. Javier Dillon Long javidil@hotmail.com

    Algoritmo de Ordenamiento

    Tenemos un grupo de registros a ordenar.

    Creamos un arreglo para dirigir el ordenamiento que se llaman cabeceras, cada cabecera corresponde a la dirección del primer registro de un grupo ordenado de registros, por ejemplo se tiene la serie a ordenar de menor a mayor con los siguientes datos: a[10]= {2, 50, 25, 30, 35, 100, 85, 65, 27, 30}.

    Las cabeceras serían C(1)=1, C(2)=3, C(3)=7, C(4)=8, C(5)=9. Correspondientes a los valores de registros 2, 25, 85, 65, 27

    La cantidad de arrays (arreglos) necesarios son: el arreglo original "a", el arreglo que contenga las cabeceras "C" y el arreglo temporal para el merge "T", y algunos índices para poder poder ejecutar el sort.

    Ahora a ordenar de menor a mayor.

    IDEA INICIAL-01

    PRIMERA PARTE

    i = 1 ; contador de registros del arreglo "a"

    imax = xxx ; cantidad de registros a ordenar de "a"

    j = 0 ; contador para el arreglo de cabeceras "C"

    Do while i < imax

    If a(i) > a(i + 1)

    c(j++) = a(i) ;

    endif

    enddo

    jmax = j ; último índice "j" usado.

    El código anterior corresponde a la primera pasada (lectura de los datos) comparando el primero con el segundo y si el primero es menor que el segundo, mantengo el primer dato como cabecera de lista,

     luego comparo el segundo con el tercero, aquí hay dos casos:

    a) si el segundo es menor o igual que el tercero, entonces mantengo la cabecera y continúo con el paso 1.

    b) si el segundo es mayor que el tercero, entonces creo una nueva cabecera de lista y continúo con el paso 1.

    Paso 1. comparo el tercero con el cuarto y ejecuto lo mismo como si fuera el segundo con el tercero y así sucesivamente hasta completar todos los elementos.

    SEGUNDA PARTE

    La segunda parte de este sort que también lo vislumbró el Ing. Rafael Estartús, después de comentarle la primera parte, fue que al obtener estas sub-listas me quedan como un quipu (la manera de contar de los incas peruanos) de datos, entonces lo que sigue es un merge (otro tipo de sort muy usado) de cada sub-lista. Y de esta manera tienes todos los datos ordenados, si quieres ver el algoritmo del merge lo puedes ver en http://mailweb.udlap.mx/~sainzmar/is211/algoritMerge.html pero esto lo puedes simplificar ya no sub-dividiendo si no uniendo dos sub-listas cada vez hasta terminar.

    k = 1 ; contador auxiliar

    Do while k < jmax

    n = 1 ; índice de arreglo "T"

    For m = 1 to C(k + 1) - 1

    T(n++) = a(m)

    Next m

    If k + 1 = jmax

    ult = imax ;

    else

    ult = C(k + 2) ;

    endif

    Do submerge ( 1, C(k + 1), ult )

    enddo

     

    quit

     

    proc submerge ; subrutina merge

    parameters ini1, ini2, ultimo

    i1 = ini1

    i2 = ini2

    do while ( ( i1 < ini2 ) .or. ( i2 < ultimo ) )

    if T(i1) <= a(i2)

    a(ini1++) = T(i1++);

    else

    a(ini1++) = a(i2++);

    endif

    enddo

    if i1 < ini2 - 1

    for i2 = i1 to ini2 - 1

    a(ini1++) = T(i1++) ;

    next i2

    endif

    Esto como idea original era bastante buena para mí. Pero después de darle algunas vueltas y haciendo cálculos mentales de cantidad de comparaciones, llegué a la segunda idea.

    IDEA 02

    El merge consume muchos recursos innecesarios, así que llegué a la conclusión que en vez de juntar la primer sub-lista con la segunda sub-lista, y lo que obtenía volver a juntarlo (merge) con la tercera sub-lista, para que de este resultado juntarlo con la cuarta sub-lista, era un consumo de muchos pasos, así que decidí hacer la siguiente mejora:

    Juntar la sub-lista-1 con la sub-lista-2, la sublista-3 con la sublista-4, la sub-lista-5 con la sub-lista-6 y así sucesivamente, de esta manera el número de procesos en comparaciones e inserciones para juntarlos se reducía. Luego se procedía las nuevas cabeceras de sub-listas con el mismo cirterio hasta terminar y tener los datos ordenados.

    Dejo al lector la aplicación de esta mejora y la siguiente en el programa inicial mostrado.

    IDEA 03

    Esta tercera mejora continuaba con la idea 02, en el sentido que en vez de la primera pasada de 1 con 2 y luego 2 con 3 para ir obteniendo cabeceras y sub-listas, esto consumía recursos, para lo cual me podía bastar comparar 1 con 2 y luego 3 con 4, obteniendo 2 sub-listas con sus cabeceras, reduciendo el número de comparaciones, para luego continuar con el paso siguiente del merge optimizado.

    Atentamente,

     

    G. Javier Dillon Long

    Telef. + 51 - 73 - 304575 (Perú)

    E-mail : javidil@hotmail.com

    Powered by Coranto

    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »