El ordenamiento por torneo es un algoritmo de ordenamiento que mejora el ordenamiento por selección ingenuo al utilizar una cola de prioridad para encontrar el siguiente elemento en el ordenamiento. En el ordenamiento por selección ingenuo, se necesitan O ( n ) operaciones para seleccionar el siguiente elemento de n elementos; en un ordenamiento por torneo, se necesitan O(log n ) operaciones (después de construir el torneo inicial en O( n )). El ordenamiento por torneo es una variación del ordenamiento por montículo .
Los ordenamientos por selección de reemplazo de torneos se utilizan para reunir las ejecuciones iniciales de los algoritmos de ordenamiento externos. Conceptualmente, se lee un archivo externo y sus elementos se introducen en la cola de prioridad hasta que la cola se llena. Luego, se extrae el elemento mínimo de la cola y se escribe como parte de la primera ejecución. Se lee el siguiente elemento de entrada y se introduce en la cola, y se selecciona nuevamente el mínimo y se agrega a la ejecución. Hay un pequeño truco: si el nuevo elemento que se introduce en la cola es menor que el último elemento agregado a la ejecución, entonces se aumenta el valor de ordenamiento del elemento para que sea parte de la próxima ejecución. En promedio, una ejecución será un 100 % más larga que la capacidad de la cola de prioridad. [1]
Los tipos de torneo también pueden usarse en fusiones de N vías.
El nombre proviene de su similitud con un torneo de eliminación simple en el que hay muchos jugadores (o equipos) que juegan en partidos de dos caras. En cada partido se comparan los jugadores y el ganador asciende para jugar un partido en el nivel superior. 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 a los que el ganador venció.
Ordenar números 72356014 (número = 8)7_ __ __ \2_ \__ \__ 7_ 7_ __2_/ \ __/ \ __/ \ \ \ \3_ 2- __ 2- __ 2- __ 3- 5- 5- 7- \3_/ \ \__/ \ \__/ \ \3_/ \ 5_/ \ __/ \ \5_/ \ __/ \ __/ \ __/ \ \ \ \ \_0 \_1 \_2 \_3 \_4 \_5 \_676_ / / / / / / / \0_ / 6_ / 6_ / __ / __ / / /0_/ \ / \ / \ / \ / \ / / /1_ 0- __ 1- 4- 4- 4- 6- 6- \1_/ \1_/ 4_/ __/ __/4_/ __/Compara: 7 + 2 + 2 + 2 + 2 + 1 + 1 = 17
Onminmax(n log n) = (ln(n) / ln(2) - 1) * n + 1En = (n - 1) + (n / 2) * (n / 4) + (n / (2 * 2) ) * (n / ( 4 * 2 )) + (n / (2 * 2 * 2) ) * (n / ( 4 * 2 * 2 )) + ...O8 = (8 - 1) + (8 / 2) * (8 / 4) + (8 / (2 * 2) ) * (8 / ( 4 * 2 ))O8 = 7 + 4 * 2 + 2 * 1 = 7 + 8 + 2 = 17
La siguiente es una implementación de ordenamiento de torneo en Haskell , basada en el código Scheme de Stepanov y Kershenbaum. [2]
importar datos.árbol -- | Adaptado de `TOURNAMENT-SORT!` en el informe de Stepanov y Kershenbaum. tournamentSort :: Ord t => [ t ] -- ^ Entrada: una lista sin ordenar -> [ t ] -- ^ Resultado: versión ordenada de la entrada tournamentSort alist = go ( pure <$> alist ) -- primero, envuelva cada elemento como un bosque de un solo árbol donde go [] = [] go trees = ( rootLabel winner ) : ( go ( subForest winner )) donde winner = playTournament trees -- | Adaptado de `TOURNAMENT!` en el informe de Stepanov y Kershenbaum playTournament :: Ord t => Forest t -- ^ Entrada forest -> Tree t -- ^ El último árbol promocionado en la entrada playTournament [ tree ] = tree playTournament trees = playTournament ( playRound trees [] ) -- | Adaptado de `TOURNAMENT-ROUND!` en el informe de Stepanov y Kershenbaum playRound :: Ord t => Forest t -- ^ Un bosque de árboles que aún no han competido en la ronda -> Forest t -- ^ Un bosque de árboles que han ganado en la ronda -> Forest t -- ^ Resultado: un bosque que contiene versiones promocionadas -- de los árboles que ganaron sus partidas playRound [ ] done = done playRound [ tree ] done = tree : done playRound ( tree0 : tree1 : trees ) done = playRoundtrees ( winner : done ) donde winner = playGame tree0 tree1 -- | Adaptado de `TOURNAMENT-PLAY!` en el informe de Stepanov y Kershenbaum playGame :: Ord t => Tree t -- ^ Entrada: ... -> Tree t -- ^ ... dos árboles -> Tree t -- ^ Resultado: `promocionar ganador perdedor`, donde `ganador` es -- el árbol con la raíz *menor* de las dos entradas playGame tree1 tree2 | rootLabel tree1 <= rootLabel tree2 = promover árbol1 tree2 | de lo contrario = promover árbol2 tree1 -- | Adaptado de `GRAB!` en el informe de Stepanov y Kershenbaum promover :: Árbol t -- ^ El `ganador` -> Árbol t -- ^ El `perdedor` -> Árbol t -- ^ Resultado: un árbol cuya raíz es la raíz de `ganador` -- y cuyos hijos son: -- * `perdedor`, -- * todos los hijos de `ganador` promover ganador perdedor = Nodo { rootLabel = rootLabel ganador , subForest = perdedor : subForest ganador } principal :: IO () principal = print $ tournamentSort listaTest donde listaTest = [ 0 , 1 , 2 , 3 , 4 , 5 ] // construye la primera pirámide de valores mínimos function pirámide_parte1_construirPyramid ( lista , i_inicio , i_fin , tamaño , cmp , intercambio ) { var i , j , k , k_fin , lvl , lvlp1 ; var pirámide = []; i = i_inicio ; j = i_inicio + 1 ; k = 0 ; lvl = 0 ; pirámide [ lvl ] = []; mientras ( j < i_end ) { if ( cmp ( lista [ i ], lista [ j ])) { swap ( lista , i , j );} pirámide [ lvl ][ k ] = i ; i += 2 ; j += 2 ; k ++ ; } if ( i < i_end ) // Puedes tener un tamaño similar al de la primera fila, por lo que solo necesitas intercambiar los valores to // (solo tienes que insertarlos en la parte 2) { if ( cmp ( lista [ i - 2 ], lista [ i ])) { tmp = lista [ i ]; lista [ i ] = lista [ i - 1 ]; lista [ i - 1 ] = lista [ i - 2 ]; lista [ i - 2 ] = tmp ; movesAdd ( 4 ); pirámide [ lvl ][ k ] = i ; } else { if ( cmp ( lista [ i - 1 ], lista [ i ])) { tmp = lista [ i ]; lista [ i ] = lista [ i - 1 ]; lista [ i - 1 ] = tmp ; movesAdd ( 3 ); }} } i_fin = k ; lvlp1 = lvl + 1 ; mientras ( i_fin > 1 ) { pirámide [ lvlp1 ] = []; k = 0 ; i = 0 ; j = 1 ; // =i+1 mientras ( j < i_fin ) { si ( cmp ( lista [ pirámide [ lvl ][ i ] ], lista [ pirámide [ lvl ][ j ] ])) { pirámide [ lvlp1 ][ k ] = pirámide [ lvl ][ j ]; i += 2 ; j += 2 ; k ++ ; continuar ;} de lo contrario { pirámide [ lvlp1 ][ k ] = pirámide [ lvl ][ i ]; i += 2 ; j += 2 ; k ++ ; continuar ;} } si ( i < i_fin ) { pirámide [ lvlp1 ][ k ] = pirámide [ lvl ][ i ]; k ++ ;} lvl ++ ; lvlp1 ++ ; i_end = k ; } return [ pirámide , lvl , pirámide [ lvl ][ 0 ], ( tamaño >> 1 ) << 1 != tamaño ]; // devuelve pirámide, último nivel, último índice, booleano para tamaño impar) } función pirámide_parte3_reconstruirPirámidePar ( pirámide , fin_nivel , bool , lista , cmp , fin_i , pos ) { var nivel , val2 , vacío = - 1 , a , b ; val2 = pirámide [ 0 ][ pos ]; para ( nivel = 0 ; nivel < fin_nivel ; nivel ++ ) { si (( pos & 0x01 ) == 0 ) { si ( pos == pirámide [ nivel ] .longitud - 1 ) { pos = pos >> 1 ; pirámide [ nivel + 1 ][ pos ] = val2 ; //val2 = val2; continuar ; } b = pirámide [ nivel ][ pos + 1 ]; a = pirámide [ nivel ][ pos ]; pos = pos >> 1 ; si ( b == vacío ) { pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; continuar ;} si ( cmp ( lista [ a ], lista [ b ])) { pirámide [ lvl + 1 ][ pos ] = b ; val2 = b ; continuar ;} pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; } de lo contrario { a = pirámide [ nivel ][ pos - 1 ]; b = pirámide [ nivel ][ pos ]; pos = pos >> 1 ; si ( a == vacío ) { pirámide [ nivel + 1 ][ pos ] = b ; val2 = b ; continuar ;} si ( cmp ( lista [ a ], lista [ b ])) { pirámide [ nivel + 1 ][ pos ] = b ; val2 = b ; continuar ;} pirámide [ nivel + 1 ][ pos ] = a ; val2 = a ; } } return [ pirámide , fin_nivel , pirámide [ fin_nivel ][ 0 ], bool ]; } // reconstruir la pirámide, reescribir la rama con un nuevo valor function Pyramid_part2_rebuildPyramid ( pirámide , lvl_end , bool , lista , cmp , i_end , i_endm3 ) { var ciclos = 0 ; var nivel , pos , val , val2 , a , b , vacío =- 1 ; val = pirámide [ lvl_end ][ 0 ]; pos = valor >> 1 ; // pozice zleva if ( bool == true && (( pos << 1 ) == i_endm3 ) && (( val & 0x01 ) == 0 ) ) // kdyz je size liche cislo a dojde k eliminaci n-2, tak posun posledni 2 cisla { bool = false ; lista [ valor ] = lista [ valor + 1 ]; lista [ val + 1 ] = lista [ val + 2 ]; mueveAgregar ( 2 ); // je sude, pak vymen za liche a prepocitej porovnani // (prepocitej vsechna nutna porovnani) pirámide [ 0 ][ pos ] = val ; // pozn.: tento kod je prepsany na funkci, protoze byl duplicitne return Pyramid_part3_rebuildPyramidEven ( Pyramid , lvl_end , bool , list , cmp , i_end , pos ); } else { if (( val & 0x01 ) == 0 ) // je sude, pak vymen za liche a prepocitej porovnani { pirámide [ 0 ][ pos ] = val + 1 ; devolver piramide_parte3_reconstruirPyramidEven ( pirámide , fin_nivel , bool , lista , cmp , fin_nivel , pos ); } else { // Si quieres, escribe una fila de valores predeterminados val2 = empty ; pirámide [ 0 ][ pos ] = val2 ; for ( nivel = 0 ; nivel < nivel_nivel ; nivel ++ ) { if (( pos & 0x01 ) == 0 ) { if ( pos == pirámide [ nivel ]. length - 1 ) { pos = pos >> 1 ; pirámide [ nivel + 1 ][ pos ] = val2 ; //val2 = val2 continue ; } a = pirámide [ nivel ][ pos ]; b = pirámide [ nivel ][ pos + 1 ]; pos = pos >> 1 ; si ( a !== vacío && b !== vacío ) { si ( cmp ( lista [ a ], lista [ b ])) { pirámide [ lvl + 1 ][ pos ] = b ; val2 = b ; continuar ;} si no { pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; continuar ;} } si ( b !== vacío ) { pirámide [ lvl + 1 ][ pos ] = b ; val2 = b ; continuar ;} pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; } else { a = pirámide [ lvl ][ pos - 1 ]; b = pirámide [ lvl ][ pos ]; pos = pos >> 1 ; if ( a !== vacío && b !== vacío ) { if ( cmp ( lista [ a ], lista [ b ])) { pirámide [ lvl + 1 ][ pos ] = b ; val2 = b ; continuar ;} else { pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; continuar ;} } if ( a !== vacío ) { pirámide [ lvl + 1 ][ pos ] = a ; val2 = a ; continuar ;} pirámide [ lvl + 1 ][ pos ] = b ; val2 = b ; } } }} devolver [ pirámide , fin_nivel , pirámide [ fin_nivel ][ 0 ], bool ]; } // principio: vyber mínimo z kazdeho paru, pak porovnej minima, minima minim ... az ziskas nejmensi cislo // pak vyrad nejmensi cislo z Pyramidy a propocitej celou vetev, opet ziskej función mínima PyramidSelectSort ( lista , inicio , fin , cmp ) { var Pyramid_data , i , x , y , endm3 = end - 3 , size = end - start ; x = lista ; y = []; Pyramid_data = Pyramid_part1_buildPyramid ( x , inicio , fin , tamaño , cmp , intercambio ); // crea una pirámide de índice a partir de valores mínimos del par i = inicio ; y [ i ] = x [ Pyramid_data [ 2 ]]; mueveAgregar ( 1 ); yo ++ ; mientras ( i < fin ) { datos_de_la_pirámide = pirámide_parte2_reconstruirPirámide ( datos_de_la_pirámide [ 0 ], datos_de_la_pirámide [ 1 ], datos_de_la_pirámide [ 3 ], x , cmp , fin , finm3 ); y [ i ] = x [ datos_de_la_pirámide [ 2 ]]; mueveAñadir ( 1 ); i ++ ; } devuelve y ; } // lista = PyramidSelectSort(lista, inicio, fin, cmp);// ---// solo para información estadística sobre movimientos, ciclos, comparaciones function movesAdd ( a ) { glob.movies + = a ; } ; function cyclesAdd ( ) { glob.cycles ++ ;}; function comparesAdd ( ) { glob.cmps ++ ;} ; función cmp ( a , b ) { comparaAdd (); devuelve a > b ;} // ---lista = [ 7 , 7 , 4 , 3 , 4 , 7 , 6 , 7 , 0 , 1 , 0 , 6 , 7 , 2 , 2 , 4 ]; var glob = { tiempo : 0 , cmps : 0 , ciclos : 0 , movimientos : 0 , intercambios : 0 , inicio : 0 , fin : lista . longitud , tamaño : 0 }; glob . tamaño = glob . fin - glob . inicio ; lista = PyramidSelectSort ( lista , glob.inicio , glob.fin , cmp ) ; /* estable rápido necesita lista.tamaño de memoria para el estado (verdadero/falso) necesita lista.tamaño de memoria para la nueva matriz */