Clever Geek Handbook

Classificação do Torneio

Continuamos a nos familiarizar com vários heaps e algoritmos de classificação usando esses heaps. Hoje temos a chamada árvore de torneios.
EDISON Software - desenvolvimento web
EDISON .




, . , .



computer science ;-)
A idéia principal da classificação do torneio é usar um heap auxiliar relativamente pequeno (em comparação com a matriz principal), que atua como uma fila de prioridade. Nesta pilha, os elementos nos níveis mais baixos são comparados, como resultado dos elementos menores (neste caso, a árvore que temos MIN-HEAP) sobem e o mínimo atual da parte dos elementos da matriz que caíram nessa pilha flutua para a raiz. O mínimo é transferido para uma matriz adicional de "vencedores", como resultado do heap compara / move os elementos restantes - e agora um novo mínimo está na raiz da árvore. Observe que, com esse sistema, o próximo valor mínimo é maior que o anterior - então uma nova matriz ordenada de "vencedores" é facilmente montada, onde novos mínimos são simplesmente adicionados ao final da matriz adicional.



Transferir os mínimos para a matriz adicional leva ao fato de lugares vazios para os seguintes elementos da matriz principal aparecerem no heap - como resultado, todos os elementos são processados ​​na ordem da fila.



A principal sutileza é que, além dos "vencedores", também existem "perdedores". Se alguns elementos já foram transferidos para a matriz "vencedores", se os elementos não processados ​​forem menores que esses "vencedores", não faz sentido filtrá-los pela árvore de torneios nesta fase - inserir esses elementos na matriz "vencedores" será muito caro (em você não pode pôr um fim neles, mas para colocá-los no início, é preciso mudar os pontos baixos já inseridos). Tais elementos que não conseguiram se encaixar na matriz de "vencedores" são enviados para a matriz de "perdedores" - eles passarão pela árvore do torneio em uma das próximas iterações, quando todas as ações forem repetidas para os demais perdedores.



Não é fácil encontrar uma implementação desse algoritmo na Internet, mas uma implementação clara e agradável em Ruby foi encontrada no YouTube. O código Java também é mencionado na seção "Links", mas não parece tão legível lá. 



  #         
  require_relative "pqueue"
	
  #     
  MAX_SIZE = 16

  def tournament_sort(array)
    #   ,   ""
    return optimal_tourney_sort(array) if array.size <= MAX_SIZE
    bracketize(array) #   ,   ""
  end
	
  #     
  def bracketize(array)
	
    size = array.size
    pq = PriorityQueue.new
    #    
    pq.add(array.shift) until pq.size == MAX_SIZE
    winners = [] #  ""
    losers = [] #  ""
		
    #      
    until array.empty?
			
      #  ""  ?
      if winners.empty?
        #      ""
        winners << pq.peek
        #     
        pq.remove 
      end
			
      #      ,   ""
      if array.first > winners.last
        pq.add(array.shift) #       
      else #        ""
        losers << array.shift #     ""
      end
			
      #     ,     ""
      winners << pk.peek unless pk.peek.nil?
      pq.remove #     
			
    end
		
    #   ,      - ?
    until pq.heap.empty?
      winners << pq.peek #     ""
      pq.remove #     
    end

    #   ""  , , ,
    #  "" -   
    return winners if losers.empty?
		
    #    ,    ""
    #   ""
    array = losers + winners
    array.pop while array.size > size
    bracketize(array) #   
		
  end
	
  #       
  def optimal_tourney_sort(array)
    sorted_array = [] #    
    pq = PriorityQueue.new
    array.each { |num| pq.add(num) } #     -
    until pq.heap.empty? #  -  
      sorted_array << pq.heap[0] 
      pq.remove #     
    end
    sorted_array #  
  end
	
  # 
  if $PROGRAM_NAME == __FILE__
    #  
    shuffled_array = Array.new(30) { rand(-100 ... 100) }
    #   
    puts "Random Array: #{shuffled_array}"
    #   
    puts "Sorted Array: #{tournament_sort(shuffled_array)}"
  end


Essa é uma implementação ingênua, na qual, após cada divisão em "perdedores" e "vencedores", essas matrizes são combinadas e, em seguida, para a matriz combinada, todas as ações são repetidas novamente. Se na matriz combinada houver elementos "perdedores" primeiro, então peneirar a pilha do torneio os ordenará junto com os "vencedores".





Essa implementação é bastante simples e intuitiva, mas você não pode chamá-la de eficaz. Os "vencedores" classificados passam pela árvore do torneio várias vezes, o que é obviamente redundante. Suponho que a complexidade do tempo aqui seja log-quadrática, O ( n log 2 n ) .



Opção de mesclagem de caminhos múltiplos



O algoritmo é visivelmente acelerado se os elementos ordenados que passaram pela peneira não forem passados ​​pelas corridas do torneio novamente.



Depois que a matriz não ordenada é dividida em "vencedores" e "perdedores" não classificados, todo o processo é repetido apenas para os "perdedores". A cada nova iteração, um conjunto de matrizes com "vencedores" será acumulado e isso continuará até que, em algum momento, não haja "perdedores". Depois disso, resta apenas mesclar todas as matrizes de "vencedores". Como essas matrizes são todas classificadas, essa mesclagem continua com o mínimo de esforço.





Nesta forma, o algoritmo já pode encontrar um aplicativo útil. Por exemplo, se você precisar trabalhar com big data, ao longo do processo de uso da pilha do torneio, serão liberados pacotes de dados ordenados com os quais você já poderá fazer algo enquanto todo o resto estiver sendo processado.



Cada um dos n elementos da matriz percorre a árvore do torneio apenas uma vez, o que leva tempo O (log n ) . Nesta implementação, o algoritmo apresenta uma complexidade de tempo pior / média O ( n log n ) .



No final da temporada



Uma série de artigos sobre classificação de heap está quase completa. Resta falar sobre os mais eficazes deles.



Ligações



Tournament sort



Priority queue



Tournament sort in Java



The Theory Behind the The Theory Behind the z/Architecture Sort Assist Instructions



Using Tournament Trees to Sort



Tournament Sort Demo Ruby



Tournament Sort Visualization



Tournament Sort Data Structure UGC NET DS



Tournament Sort Algorithm — a Heapsort variant



:






A classificação de hoje foi adicionada ao aplicativo AlgoLab, que está sendo usado - atualize o arquivo do Excel com macros.



Nos comentários da célula com o nome da classificação, você pode especificar algumas configurações.

A maneira variável é uma árvore de torneios de várias maneiras (apenas no caso, é possível torná-la não apenas binária, mas também ternária, quaternária e pentária).

A fila variável é o tamanho da fila inicial (o número de nós no nível mais baixo da árvore). Como as árvores estão cheias, se, por exemplo, com o modo = 2 você especificar a fila = 5, o tamanho da fila será aumentado para a potência mais próxima de dois (nesse caso, até 8).

Variável NWayMerge assume o valor 1 ou 0 - indica se deve ser usada uma mesclagem de caminhos múltiplos ou não.


More articles:


All Articles