Contados
Movimientos
Contadores

  • Contándose
  • Recién movida
  • En su sitio

Más sobre el ordenamiento por cuentas

Ordenamiento por cuentas

El ordenamiento por cuentas funciona cuando los valores son números enteros en un rango pequeño. Tiene un contador para cada valor posible, cuenta cuántas veces aparece cada uno y, con esas cuentas, sabe exactamente dónde va cada valor. Mira cómo se llenan los contadores al leer la lista y cómo se vacían de nuevo a medida que cada valor pasa a su tramo, movimiento a movimiento. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de movimiento en movimiento. Arrastra el control de pasos para saltar a cualquier punto. La franja entre la lista y la fila del búfer tiene un contador para cada valor. Los recuadros muestran los valores contados, los movimientos y los contadores. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige cuántas barras hay y cómo empiezan, o escribe tus propios números enteros. Prueba una lista con pocos valores distintos.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar de valor en valor. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
  3. Observa los contadores: se llenan mientras se lee la lista y luego bajan a medida que se coloca cada valor.

Cómo funciona el ordenamiento por cuentas

Crea un contador para cada valor, del menor al mayor. Lee la lista una vez y suma uno al contador de cada valor que veas. Luego suma las cuentas desde el valor menor: el tramo de un valor empieza justo después de todos los valores menores. Por último, recorre la lista de nuevo, mueve cada valor al siguiente lugar libre de su tramo y copia el resultado de vuelta.

Rápido en un rango pequeño

El ordenamiento por cuentas lee la lista dos veces y recorre los contadores una vez, así que su trabajo crece con n + k: el número de valores más el número de contadores. Con muchos valores en un rango pequeño, como notas de examen de 0 a 100 o edades, supera a cualquier ordenamiento por comparación. Con un rango amplio derrocha tiempo y memoria en contadores que nadie usa: tres valores repartidos entre 1 y 1.000.000 necesitarían un millón de contadores. También es el paso que el ordenamiento radix repite para cada dígito.

Preguntas frecuentes

¿Cómo funciona el ordenamiento por cuentas?

Cuenta cuántas veces aparece cada valor, suma las cuentas para saber dónde empieza el tramo de cada valor y luego mueve cada valor directamente al siguiente lugar libre de su tramo. Nunca compara dos valores.

¿Cuándo conviene usar el ordenamiento por cuentas?

Cuando los valores son números enteros, o se pueden convertir en ellos, y el rango del menor al mayor no es mucho mayor que el número de valores: notas, edades, códigos pequeños. Entonces tarda un tiempo proporcional a n + k.

¿Es estable el ordenamiento por cuentas?

Sí, cuando los valores se mueven en el orden de la lista al siguiente lugar libre de su tramo, como aquí. Eso es lo que permite al ordenamiento radix usarlo para cada dígito.

¿Por qué no escribir cada valor tantas veces como se contó?

Con números sin más funciona, y es incluso más sencillo. Pero los datos reales suelen llevar más que la clave, como un nombre junto a cada nota, y al escribir las claves contadas eso se perdería. Mover los propios elementos mantiene todo unido.

¿Se envían mis números a algún sitio?

No. La ordenación se hace en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor