Counting Sort (Ordenamiento por cuentas)

Definición

Este algoritmo es muy interesante porque no usa ninguna sentencia if, es decir, no hay ninguna condición, a excepción de los bucles. El algoritmo funciona mejor con una lista larga, de un solo elemento simple: no hay structs, y de números repetitivos. Es mejor que los números no se separen mucho entre sí; por ejemplo, el valor máximo sea de 10, y el mínimo de 1, aunque tengamos 10.000 entradas (o elementos). La desventaja de este algoritmo es la necesidad de almacenar muchos datos en memoria.

Funciona contando el número de objetos que tienen cada clave distinta y el uso de la aritmética en esos recuentos para determinar las posiciones de cada valor clave en la secuencia de salida. Su tiempo de ejecución es lineal en el número de elementos y la diferencia entre los valores clave máximo y mínimo, por lo que solo es adecuado para uso directo en situaciones donde la variación en las claves no es significativamente mayor que el número de elementos. Sin embargo, a menudo se usa como una subrutina en otro algoritmo de clasificación, la clasificación por radix, que puede manejar claves más grandes de manera más eficiente

Seudocódigo

Símbolo	Significado
A	Lista principal o de entrada
B	Lista final u ordenada
C	Lista de contabilidad o de frecuencia
k	Valor máximo en A

El pseudocódigo es el siguiente:

Ordenamiento_por_Cuenta( A, B, k )
 1  for i <-- 1 to k
 2    do C[i] <-- 0
 3  for j <-- 1 to tamaño[A]
 4    do C[ A[j] ] <-- C[ A[j] ] + 1
 5  // C[i] contiene ahora el número de elementos igual a 'i'
 6  for i <-- 2 to k
 7    do C[i] <-- C[i] + C[i-1]
 8  // C[i] contiene ahora el número de elementos menor que o igual a 'i'
 9  for j <-- tamaño[A] downto 1
10    do B[ C[ A[j] ] ] <-- A[j]
11       C[ A[j] ] <-- C[ A[j] ] - 1

Github

https://github.com/ingenierajessica/Algoritmos/blob/master/Counting%20Sort.ipynb

Ejemplo

Veamos un ejemplo:

0.  C es inicializada asignando todos elementos a cero (pasos 1-2).
1.  Empezamos con una lista desordenada, A, de números enteros que se repiten varias veces.
2.  C es asignada valores que representan la cuenta de cada elemento de A (pasos 3-4). El índice de C representa el elemento de A: 0 unos, 0 doses, 3 treses, y 2 cuatros.

3.  C es asignada a cada elemento la suma de su valor y el del elemento anterior (pasos 6-7); por ejemplo, C[3] = C[3] + C[2], etc.. Esto sirve para saber en qué índice acaba el bloque de números repetidos: C[3] = 3 => bloque de treses acaba en índice 3, C[4] = 5 => bloque de cuatros acaba en índice 5.

4.  B es la lista ordenada de A. Es asignada el primer número ordenada: 3 (pasos 9-10), con j = 5.

5.  El elemento de C usado para ordenar B es restado 1 (paso 11).
6.  B es asignada otro valor en orden (pasos 9-10), con j = 4.

7.  C es nuevamente restada 1 al elemento recién usado (paso 11).
8.  B es añadida otro número en su propio sitio, con j = 3.

9.  Se repite paso 11.
10. Pasos 9-10, con j = 2.

11. Paso 11.
12. Pasos 9-10, con j = 1.

13. Ningún elemento de C tendrá un valor negativo.

14. j = 0, por lo tanto se sale del bucle for. B da lugar al resultado, que es el ordenamiento de A:

Material de apoyo

Learn Counting Sort Algorithm

Merge Sort

Definición

Consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente pequeños o triviales.

Pasos

1. Ordenar una secuencia S de elementos:
   1. Si S tiene uno o ningún elemento, está ordenada
   2. Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros n/2, y S2 los restantes.
   3. Ordenar S1 y S2, aplicando recursivamente este procedimiento.
   4. Mezclar S1 y S2 ordenadamente en S
2. Mezclar dos secuencias ordenadas S1 y S2 en S:
1. Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2).
2. Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

GitHub

El código en Python se encuentra en la siguiente ruta:

https://github.com/ingenierajessica/Algoritmos/blob/master/Merge%20Sort.ipynb

Seudocódigo

MergeSort (T [ ] a,  entero n) 
{ 
 si ( n>1) entonces 
 { 
  a1= a[0...n/2 -1] ; // Primera mitad 
  a2= a[n/2...n-1] ; // Segunda mitad 
  MergeSort(a1, n/2);
  MergeSort(a2, n – n/2); 
  Merge(a1,a2,a, n); 
 }
} 

Merge(T [ ] a1,T [ ] a2, T [ ] a, entero n)
{ 
 entero i, j, k; 
 i = j = k =0; 
 mientras(i < n/2 && j < n - n/2)
 { 
  si(a1[i] < a2[j]) entonces
  { 
  b[k] = a1 [i]; 
  i++; k++;
  }  
  sino
  { 
  b[k] = a2[j]; 
  j++; k++;
  } 
 }
 mientras(i < n/2)
 { 
  b[k] = a1 [i]; 
  i++; k++;
 }  
 mientras(j < n-n/2)
 { 
  b[k] = a2 [j]; 
  j++; k++;
 }  
}   

Ejemplo algoritmo

Complejidad del algoritmo

Para ordenar un arreglo de tamaño n se ordenan 2 arreglos de tamaño n/2, de aquí el 2T(n/2), y luego se consume O(n) en realizar la mezcla. Resolviendo la ecuación recurrente tenemos que T(n) = O(n log n)

Propiedades

• Es Estable.
• Memoria Auxiliar O(n).
• No ordena en el lugar.
• Es O(n log n).

Mezclas Sucesivas (MergeSort)

Fue desarrollado en 1945 por John Von Neumann. Se aplica la técnica divide y vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada. Si n = 1 solo hay un elemento por ordenar, sino se hace una ordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se ordenan de igual forma.

MergeSort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. MergeSort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar MergeSort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos como quicksort den un bajo rendimiento, y para otros como heapsort sea algo imposible. El algoritmo de MergeSort es un algortimo de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el algoritmo no depende de la disposición inicial de los elementos del vector. En segundo lugar es un algoritmo que requiere de un espacio extra de almacenanimiento para poder funcionar.

Fuente

• Curso de programación II, Universidad de Ciencias Informáticas.
• PEÑA M., Ricardo. Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1998.
• WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.
• WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.

Cotas Inferiores de un Algoritmo

¿Qué es un algoritmo?

La definición más general, es que un algoritmo es simplemente una secuencia de pasos, que seguidos de forma precisa producen un resultado predecible, y que son aplicables a problemas similares.

Una manera de explicarlo es con la metáfora de las recetas de cocina. Cada receta es un algoritmo, que contiene los pasos para preparar un plato. Si una persona conoce y ha seguido muchas recetas, tendrá a sus disposición un arsenal de “conocimiento” y “experiencia” que le permitirán atacar problemas nuevos, como por ejemplo tener que cocinar con las limitaciones de una cocina/despensa en particular y un número de comensales. De la misma forma, un programador que haya estudiado algoritmos comunes y cómo analizarlos, tendrá a su disposición una mayor caja de herramientas a la hora de enfrentar problemas lógicos, llevarlos a código y analizar su eficiencia.

 

¿Notación Asintótica?

Hemos quedado en que los algoritmos son secuencias de pasos que podemos seguir para solucionar problemas concretos. Pero no sólo eso, sino que también hemos dicho que son como “recetas”, y esto quiere decir que no son “cualquier” secuencia de pasos, sino una que has sido “probada” (funciona correctamente) y “perfeccionada” (es eficiente).

Este último punto, la eficiencia, nos lleva a la temible “notación asintótica”. Siendo un concepto teórico, no voy a entrar en los detalles matemáticos, eso lo pueden encontrar en los links al final, si no ver algunos ejemplos que puedan servir para ilustrar los conceptos en líneas generales.

En computación, la notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de operaciones llevadas a cabo no varíe según crezca la entrada.

Notaciones comunes en orden de eficiencia:

• O(1)
• O(log(n))
• O(n)
• O(n * log(n))
• O(n^2)
• O(2^n)

Apoyo Web

http://webdiis.unizar.es/asignaturas/TAP/material/eficiencia.pdf

Videos

Notación Asintótica


¿Qué es un algoritmo y por qué debería importarte?