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:
Viernes 29 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
  • Análisis sobre la divulgación en el ordenamiento jurídico cubano de las voluntades anticipadas: ...
  • 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 de la Práctica 5. La longitud de L es Par. Programación. Algoritmos.
  • Algoritmo de Ordenamiento: Distintos pasos para crear un Algoritmo de Ordenamiento si tenemos un grupo de registros a ordenar.

  • Enlaces externos relacionados con Algoritmo ordenamiento


    Autor: 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

    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 »