Algoritmos de Ordenamiento



Los siguientes son los aspectos más importantes y una descripción de los algoritmos expuestos en clase:

Ordenamiento Rápido

 Notas importantes
  • Utiliza la técnica de divide y vencerás.
  • Se utiliza un elemento de pivote elegido de manera aleatoria que se usa como referencia para el funcionamiento del algoritmo.
  • De manera usual el pivote es el primer o último elemento de la lista, pero puede ser elegido de manera aleatoria.
Algoritmo
  1. Si la lista es de largo 1 se considera ordenada.
  2. Se elige el pivote.
  3. Se coloca el pivote en su posición correcta colocando los valores menores a él y los mayores a él en lados diferentes.
  4. Repetir los pasos 1-3 de manera recursiva en las sublistas a los lados del pivote.
Simulación de los pasos 1 - 3.

Ordenamiento de Cajón

 Notas importantes
  • Es más útil y eficiente cuando los elementos de entrada están uniformemente distribuidos en un rango.
  • Se crea un vector vacío que maneja los rangos en que se pueden clasificar los elementos del vector a ordenar.
Algoritmo
  1. Se crea un vector con largo de acuerdo a los rangos en que se van a clasificar los elementos (vector de cajones).
  2. Se distribuyen los elementos en los diferentes cajones.
  3. Se utiliza un algoritmo de ordenamiento (eje. inserción) para ordenar los elementos de cada cajón.
  4. Se reconstituyen los sub-vectores de cada cajón en un sólo vector.

Representación visual de la distribución de elementos en los diferentes cajones.


Ordenamiento de Inserción

 Notas importantes
  • Una analogía es el proceso a ordenar los naipes de la mano en un juego de cartas.
  • Se utiliza una referencia/índice para definir la parte ordenada conforme se avanza en el algoritmo.
Algoritmo
  1. Se toma el elemento que sigue a la parte ordenada.
    • Si es el primer elemento se considera ordenado.
    • Alternativamente se puede iniciar con el segundo elemento si el largo de la lista es mayor que 1.
  2. Se recorre el subvector ordenado para determinar la posición del elemento evaluado.
  3. Se inserta el elemento en la posición que le corresponde.
  4. Se ajusta la referencia que determina el subvector ordenado.
  5. Se repiten los pasos 1 - 4 hasta que el subvector ordenado sea del mismo tamaño que el vector original.
Animación del algoritmo de inserción.



Ordenamiento de Burbuja

 Notas importantes
  • Ordenamiento de intercambio más simple.
  • Se determina que la lista está ordenada cuando hay un recorrido limpio (sin intercambios).
Algoritmo
  1. Se configura una referencia/índice al inicio del vector.
  2. Verificar que no sea el final de la lista.
  3. Se compara el elemento de la posición actual con el siguiente y se determina el mayor o menor dependiendo del tipo de ordenamiento.
  4. Se incrementa la referencia/índice en 1.
  5. Se repiten los pasos del 1-4 hasta llegar al final de la lista.
  6. Se ajusta el nuevo final de la lista, ya que el último elemento se considera ordenado.
  7. Se repiten los pasos del 1-5 hasta que suceda un recorrido sin intercambios.
Simulación del ordenamiento de burbuja con bandera.



Ordenamiento Heap

Notas importantes
  • Utiliza dos funciones para trabajar en un maxHeap:
    • crearMaxHeap - contruye un heap de tipo max. Es decir un árbol binario completo donde cada nodo es mayor o igual a sus nodos hijos.
    • heapify - para modificar el heap de manera que vuelva a ser un maxHeap cuando se remueve la raíz.

  • Con el maxHeap se van colocando los valores mayores (o menores si fuera un minHeap) al final del subvector no ordenado hasta que el heap esté vacío.
Algoritmo
  1. Se crea un maxHeap o minHeap.
  2. Se coloca una referencia/índice al final del vector no ordenado para ir introduciendo el elemento mayor/menor del heap.
  3. Se coloca la raíz al final de la lista y el último nodo del heap en la raíz.
  4. Se ajusta la referencia/índice una posición menos que sería el nuevo final del subvector no ordenado.
  5. Se realiza un heapify.
  6. Se repiten los pasos del 3 - 5, hasta que el heap esté vacío y por lo tanto el vector final está ordenado.

Simulación del ordenamiento heap.



Ordenamiento de Unión (Merge)

Notas importantes
  • Este también se basa en el concepto de divide y vencerás.
  • Se realizan dos operaciones sobre el vector inicial y posteriores subvectores: división y merge (en subvectores ordenados).
Algoritmo
  1. Se divide el vector en 2 subvectores: izquierdo y derecho.
  2. Se continúa dividiendo hasta que ambos sean de largo 1 (se consideran ordenados) y se realiza una unión de ambos subvectores en un nuevo vector ordenado.
  3. Los subvectores ordenados resultantes se vuelven a unir evaluando la relación de peso de sus elementos para colocarlos en un nuevo subvector ordenado.
  4. Se repite el paso 3 hasta que se los subvectores unidos devuelvan el vector original ordenado.

Simulación del algoritmo de unión (Merge).





Ordenamiento Radix

Notas importantes
  • Se hacen diferentes pasadas de ordenamiento evaluando diferentes dígitos de cada número conforme el algoritmo progresa.
Algoritmo
  1. Se determina el mayor elemento para saber cuántos dígitos se deben evaluar.
  2. Se ordenan los elementos de acuerdo al dígito menos significativo (de menor peso).
  3. Se ordena el vector resultante de acuerdo al dígito de mayor peso siguiente.
  4. Se repite el paso 3 hasta evaluar todos los dígitos de los elementos del vector.

Imagen que demuestra los diferentes recorridos de ordenamiento sobre los diferentes dígitos de cada número.



Ejercicio prácticos asignados en clase

Radix - A. [33, 95, 72, 12, 5, 100, 85, 302, 23, 81]
  • Se ordena la lista de acuerdo al primer dígito:
    • [100, 81, 72, 12, 302, 33, 23, 95, 5, 85]
  • Se ordena la lista de acuerdo al segundo dígito:
    • [100, 05, 302, 12, 23, 33, 72, 81, 85, 95]
  • Se ordena la lista de acuerdo al tercer dígito:
    • [005, 012, 023, 033, 072, 081, 085, 095, 100, 302]
  •  La lista ahora está ordenada:
    • [5, 12, 23, 33, 72, 81, 85, 95, 100, 302] 

Burbuja - E. [z, l, j, e, r, d, r, o]
  • Primer recorrido:
    •  [l, z, j, e, r, d, r, o]
    •  [l, j, z, e, r, d, r, o] *Cambio
    •  [l, j, e, z, r, d, r, o] *Cambio
    •  [l, j, e, r, z, d, r, o] *Cambio
    •  [l, j, e, r, d, z, r, o] *Cambio
    •  [l, j, e, r, d, r, z, o] *Cambio
    •  [l, j, e, r, d, r, o, z] *Cambio
  •  Segundo recorrido:
    •  [l, j, e, r, d, r, o, z]
    •  [j, l, e, r, d, r, o, z] *Cambio
    •  [j, e, l, r, d, r, o, z] *Cambio
    •  [j, e, l, r, d, r, o, z]
    •  [j, e, l, d, r, r, o, z] *Cambio
    •  [j, e, l, d, r, r, o, z]
    •  [j, e, l, d, r, o, r, z] *Cambio
  • Tercer recorrido: 
    •  [j, e, l, d, r, o, r, z]
    •  [e, j, l, d, r, o, r, z] *Cambio
    •  [e, j, l, d, r, o, r, z]
    •  [e, j, d, l, r, o, r, z] *Cambio
    •  [e, j, d, l, r, o, r, z]
    •  [e, j, d, l, o, r, r, z] *Cambio
  • Cuarto recorrido:
    •  [e, j, d, l, o, r, r, z]
    •  [e, j, d, l, o, r, r, z]
    •  [e, d, j, l, o, r, r, z] *Cambio
    •  [e, d, j, l, o, r, r, z]
    •  [e, d, j, l, o, r, r, z]
  • Quinto recorrido:
    •  [e, d, j, l, o, r, r, z]
    •  [d, e, j, l, o, r, r, z] *Cambio
    •  [d, e, j, l, o, r, r, z]
    •  [d, e, j, l, o, r, r, z]
  • Sexto recorrido:
    •  [d, e, j, l, o, r, r, z]
    •  [d, e, j, l, o, r, r, z]
    •  [d, e, j, l, o, r, r, z]
    •  
  • Séptimo recorrido:
    •  [d, e, j, l, o, r, r, z]
    •  [d, e, j, l, o, r, r, z]
  • Lista ordenada
    •  [d, e, j, l, o, r, r, z] 

Merge - G. [505, 404, 606, 101, 707, 808, 202, 909, 303]
  • Se divide el arreglo recursivamente y se ordenan los subvectores:
    • [505, 404, 606, 101, 707, 808, 202, 909, 30]
    • [505, 404, 606, 101, 707] [808, 202, 909, 303]
    • [505, 404, 606] [101, 707] [808, 202, 909, 303]
    • [505, 404] [606] [101, 707] [808, 202, 909, 303]
    • [505] [404] [606] [101, 707] [808, 202, 909, 303]
      • [404, ] [606] [101, 707] [808, 202, 909, 303]
      • [404, 505] [606] [101, 707] [808, 202, 909, 303]
    • [404, 505] [606] [101, 707] [808, 202, 909, 303]
      • [404, ] [101, 707] [808, 202, 909, 303]
      • [404, 505] [101, 707] [808, 202, 909, 303]
      • [404, 505, 606] [101, 707] [808, 202, 909, 303]
    • [404, 505, 606] [101] [707] [808, 202, 909, 303]
      • [404, 505, 606] [101] [808, 202, 909, 303] 
      • [404, 505, 606] [101, 707] [808, 202, 909, 303]
    • [404, 505, 606] [101, 707] [808, 202, 909, 303]
      • [101] [808, 202, 909, 303]
      • [101, 404] [808, 202, 909, 303]
      • [101, 404, 505] [808, 202, 909, 303]
      • [101, 404, 505, 606] [808, 202, 909, 303]
      • [101, 404, 505, 606, 707] [808, 202, 909, 303]
    • [101, 404, 505, 606, 707] [808, 202, 909, 303]
    • [101, 404, 505, 606, 707] [808, 202] [909, 303]
    • [101, 404, 505, 606, 707] [808] [202] [909, 303]
      •  [101, 404, 505, 606, 707] [202] [909, 303]
      •  [101, 404, 505, 606, 707] [202,808] [909, 303]
    • [101, 404, 505, 606, 707] [202,808] [909, 303]
    • [101, 404, 505, 606, 707] [202,808] [909] [303]
      • [101, 404, 505, 606, 707] [202,808] [303]
      • [101, 404, 505, 606, 707] [202,808] [303, 909]
    • [101, 404, 505, 606, 707] [202,808] [303, 909]
      • [101, 404, 505, 606, 707] [202]
      • [101, 404, 505, 606, 707] [202, 303]
      • [101, 404, 505, 606, 707] [202, 303, 808]
      • [101, 404, 505, 606, 707] [202, 303, 808, 909]
         
    • [101, 404, 505, 606, 707] [202, 303, 808, 909]
      • [101]
      • [101, 202]
      • [101, 202, 303]
      • [101, 202, 303, 404]
      • [101, 202, 303, 404, 505]
      • [101, 202, 303, 404, 505, 606]
      • [101, 202, 303, 404, 505, 606, 707]
      • [101, 202, 303, 404, 505, 606, 707, 808]
      • [101, 202, 303, 404, 505, 606, 707, 808, 909]
  • Lista ordenada:
    • [101, 202, 303, 404, 505, 606, 707, 808, 909]

    Comments

    Post a Comment

    Popular Posts