Ordenamiento por cuentas

Ordenamiento por cuentas

El ordenamiento por cuentas (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Sólo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo).

El primer paso consiste en averiguar cuál es el intervalo dentro del que están los datos a ordenar (valores mínimo y máximo). Después se crea un vector de números enteros con tantos elementos como valores haya en el intervalo [mínimo, máximo], y a cada elemento se le da el valor 0 (0 apariciones). Tras esto se recorren todos los elementos a ordenar y se cuenta el número de apariciones de cada elemento (usando el vector que hemos creado). Por último, basta con recorrer este vector para tener todos los elementos ordenados.

Contenido

Ejemplo

Considérese la siguiente lista de números:

 Lista sin ordenar: 2, 5, 3, 2, 7, 5, 3, 2, 2

Para ordenarla con este algoritmo, seguimos estos pasos:

  • Buscar el mínimo y el máximo
 Mínimo = 2
 Máximo = 7
  • Crear el vector auxiliar
 vaux = nuevo vector(2,7) de enteros
  • Recorrer la lista de números y contar elementos, debe fijarse como el valor en la lista de entrada se usa como índice en el vetor auxiliar
 Al final, 
   vAux(2) = 4  porque aparece 4 veces en la lista
   vAux(3) = 2    "       "    2   "          "
   vAux(4) = 0  porque no aparece en la lista ninguna vez
   vAux(5) = 2  porque aparece 2 veces en la lista
   vAux(6) = 0  porque no aparece en la lista ninguna vez
   vAux(7) = 1  porque aparece 1 vez en la lista 
  • Recorriendo el vector auxiliar obtenemos la lista de números ordenada
   listaValores(0) = 2  El valor 2, se repite 4 veces.
   listaValores(1) = 2
   listaValores(2) = 2
   listaValores(3) = 2
   -
   listaValores(4) = 3  El valor 3 se repite 2 veces
   listaValores(5) = 3
   -
   listaValores(6) = 5  El valor 5 se repite 2 veces
   listaValores(7) = 5  
   -
   listaValores(8) = 7  El valor 7 sólo aparece 1 vez
   -
   -
   Lista ordenada = 2, 2, 2, 2, 3, 3, 5, 5, 7

Características

Se trata de un algoritmo estable cuya complejidad computacional es O(n+k), siendo n el número de elementos a ordenar y k el tamaño del vector auxiliar (máximo - mínimo).

La eficiencia del algoritmo es independiente de lo casi ordenado que estuviera anteriormente. Es decir no existe un mejor y peor caso, todos los casos se tratan iguales.

El algoritmo counting, no se ordena in situ, si no que requiere de una memoria adicional.

Limitaciones

El algoritmo posee una serie de limitaciones que obliga a que sólo pueda ser utilizado en determinadas circunstancias.

Sólo ordena números enteros, no vale para ordenar cadenas y es desaconsejable para ordenar números decimales. Teóricamente se puede, pero debería recrear en la matriz auxiliar tantas posiciones como decimales quepan entre 2 números onsecutivos, si se restringe a 1 o 2 decimales podría ser asequible un número mayor de decimales puede llegar a suponer una memoria auxiliar impracticable.

Otra limitación (por ineficiencia) incluso con números enteros es cuando el rango entre el mayor y el menor es muy grande. Imaginemos una lista de 1000 elementos, donde el menor es el 0 y el mayor 123456789. Ordenar esta lista supondría crear una matriz auxiliar de 123456790 elementos. Una cantidad muy elevada de memoria para ordenar sólo 1000 elementos. También supondría un desperdicio de tiempo pués la matriz auxiliar para trasvasar a la lista ordenada debe recorrerse entera, aunque sólo se reasignarán 1000 valores de los 123456790 elementos.

Con lenguajes de programación que no permitan definir vectores cuyo primer índice sea un valor distinto de 0 ó 1 es necesario realizar una traducción de los valores. Por ejemplo, si el intervalo es (4,10) y el vector auxiliar comprende el rango (1-7), para cada elemento se deberá incrementar el contador de la posición en 3.

Un modo de hacer este algoritmo más práctico, es guardar varios elementos en un índice de la matriz, pero en este caso la matriz ya no es de valores enteros sino que contiene algún tipo de estructura de datos. Así es posible por ejemplo ordenar números con decimales. Por ejemplo si en la matriz auxiliar en el índice 5, metemos todas las apariciones de la lista cuyo valor está en el rango 5.0 - 5.99. Luego con cada elemento en cada índice se realiza un nuevo ordenamiento. cuando se usan este tipo de técnicas, el algoritmo ya se considera otro, denominado: bucket sort.

Pseudocódigo

Se han añadido los comentarios pertinenetes para aclarar las partes que fueren más dudosas.

   comentario: listaValores es una matriz de valores enteros.
   Entrada Función counting_sort(listaValores)
      ListaVariables
         minValor    comentario: el valor del elemento menor en la lista
         maxValor    comentario: el valor del elemento mayor en la lista
         vAux        comentario: una matriz de elementos auxiliar de tanto elementos como 
                                  define el rango minValor a maxValor 
         i, j, n     comentario: contadores de bucle
         valor       comentario: valor del elemento actual en el bucle
         tamaño      comentario: cantidad de elementos en listaValores
 
      Previos      
         comentario: Buscar valor mínimo y máximo
         LlamadaaFuncion BuscarLimites(listaValores, minValor, maxValor)
 
         comentario: Crea el vector auxiliar, con todos sus elementos a 0
         vAux = NuevoVector(minValor,maxValor)
 
         comentario: Obtiene la cantidad de elementos que contiene la matriz
         tamaño = TotalElementosEn(listaValores)
 
         comentario: Contar elementos. En el índice expresado por el valor, se van contando
                     las veces que aparece dicho valor en la matriz de entrada 
         comentario: Este bucle realiza una matriz de conteo, cada valor indica cuantas veces
                     aparece el valor representado por el índice en la lista de valores.
      Inicio   
         i = 0 
         Hacer Mientras (i < tamaño)
              valor = listaValores(i)
              vAux(valor] = vAux(valor) + 1
              i = i + 1
         Repetir
 
         comentario: Trasvasar la matriz de conteo a la lista, que queda así ya ordenada
 
         i = minValor 
         j = 0
         Hacer Mientras (i < maxValor)
            comentario: Si para el índice 'i' se contó 1 o más elementos, transferir a la lista  
            Si vAux(i) > 0 Entonces       
               Para n Repetir Desde 1 Hasta vAux(i) 
                  listaValores(j) = i 
                  j = j + 1
               Siguiente n
            Fin si
         Repetir 
      Fin
   Salida Funcion
 
 
   comentario: Esta función auxiliar busca y devuelve el mayor y menor elementos de una matriz
   Entrada Funcion BuscarLimites(listaValores, minValor, maxValor)
      Variables
         i      comentario: contador del bucle        
 
      Inicio
         minValor = listaValores(0)
         maxValor = minValor
 
         Para i Repetir Desde 1 Hasta TotalElementosEn(ListaValores)
            Si listaValores(i) < minValor entonces 
               minValor = listaValores(i)
            Ó Si listaValores(i) > maxValor entonces
               maxValor = listaValores(i)
            Fin Si
         Siguiente i
      Fin                 
   Salida Funcion

Implementaciones

El algoritmo Counting Sort en Perl para valores entre 0 y $max

sub counting_sort {
    my ($array, $max) = @_;    # Todos los elementos de @$array deben estar en el rango 0..$max.
    my @contador = (0) x ($max+1);
    foreach my $elemento ( @$array ) { $contador[ $elemento ]++ }
    return map { ( $_ ) x $contador[ $_ ] } 0..$max;
}

Referencias

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.2: Counting sort, pp.168–170.
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2, Sorting by counting, pp.75–80.
  • Seward, Harold H. Information sorting in the application of electronic digital computers to business operations Masters thesis. MIT 1954.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Tribunal de Cuentas (España) — Sede del Tribunal de Cuentas de España, en Madrid. En España, el Tribunal de Cuentas es el supremo órgano fiscalizador de las cuentas y de la gestión económica del Estado y del sector público, sin perjuicio de su propia jurisdicción, de acuerdo… …   Wikipedia Español

  • Casos de pederastia por miembros de la Iglesia católica — Saltar a navegación, búsqueda A finales de la década de 1990 comenzaron a salir a la luz denuncias contra sacerdotes y religiosos católicos, principalmente en Estados Unidos y Australia, acusados de abusos sexuales a menores, cometidos durante la …   Wikipedia Español

  • Algoritmo de Kruskal — El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el… …   Wikipedia Español

  • Constitución española de 1978 — Ejemplar de la Constitución conservado en el Congreso de los Diputados. Creación 31 de octubre de 1978 Ratifi …   Wikipedia Español

  • Wikipedia:Café (todos) — Atajos WP:CWP:C …   Wikipedia Español

  • Venezuela — Para otros usos de este término, véase Venezuela (desambiguación). República Bolivariana de Venezuela …   Wikipedia Español

  • Jurisdicción Contencioso-Administrativa de España — La Jurisdicción Contencioso Administrativa de España es el orden jurisdiccional, integrado en el Poder Judicial, al que la Constitución encomienda el control jurisdiccional de la potestad de dictar actos por parte de la Administración Pública, y… …   Wikipedia Español

  • Secretaría de Justicia y Derechos Humanos de Honduras — La Secretaría de Justicia y Derechos Humanos de Honduras es la institución del Poder Ejecutivo con la capacidad de orientar técnicamente a las y los funcionarios del Poder Ejecutivo e instituciones del Estado para que enmarquen su comportamiento… …   Wikipedia Español

  • Unión Europea — «UE» redirige aquí. Para otras acepciones, véase UE (desambiguación). Unión Europea Europäische Union …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”