La clasificación de torneo es un algoritmo de clasificación . Mejora la clasificación de selección ingenua mediante el uso de una cola de prioridad para encontrar el siguiente elemento en la clasificación. En la ordenación de selección ingenua, se necesitan O ( n ) operaciones para seleccionar el siguiente elemento de n elementos; en un tipo de torneo, se necesitan operaciones O (log n ) (después de construir el torneo inicial en O ( n )). El tipo de torneo es una variación de heapsort .
Las clasificaciones de selección de reemplazo de torneo se utilizan para recopilar las ejecuciones iniciales para algoritmos de clasificación externos. Conceptualmente, se lee un archivo externo y sus elementos se insertan en la cola de prioridad hasta que se llena. Luego, el elemento mínimo se extrae de la cola y se escribe como parte de la primera ejecución. El siguiente elemento de entrada se lee y se coloca en la cola, y el mínimo se selecciona de nuevo y se agrega a la ejecución. Hay un pequeño truco que indica que si el nuevo elemento que se inserta en la cola es menor que el último elemento agregado a la ejecución, entonces el valor de clasificación del elemento aumenta para que sea parte de la siguiente ejecución. En promedio, una ejecución será un 100% más larga que la capacidad de la cola de prioridad. [1]
El nombre proviene de su similitud con un torneo de eliminación simple donde hay muchos jugadores (o equipos) que juegan en partidos de dos caras. Cada partido compara a los jugadores, y el jugador ganador es ascendido para jugar en el siguiente nivel. La jerarquía continúa hasta que el partido final determina al ganador final. El torneo determina al mejor jugador, pero el jugador que fue derrotado en el partido final puede no ser el segundo mejor; puede ser inferior a otros jugadores al que derrotó el ganador.
La siguiente es una implementación de la clasificación de torneos en Haskell , basada en el código Scheme de Stepanov y Kershenbaum. [2]