Análise experimental do quicksort probabilístico com gerador de números pseudo-aleatórios penta-independente

Abstract

Resumo: Estudamos, neste trabalho, diversas variações do Quicksort com relação à otimização do cache e percebemos que tal preocupação limita muito o algoritmo e as diferenças resultantes são extremamente específicas com relação à arquitetura utilizada ou simulada. Estudamos então variações do Quicksort que têm como foco modificar a forma de escolha do pivô com o objetivo de minimizar o número de comparações e trocas. Dentre as variações estudadas, os Quicksort probabilísticos caracterizam-se por usarem números pseudo-aleatórios na escolha do pivô. Concentramos-nos então em estudar dois algoritmos geradores de números pseudo-aleatórios (GNPA), um por congruência linear, proposto por Knuth em [Knu00b], e outro penta-independente proposto por Howard Karloff em [KR93]. Analisamos, comparamos e testamos esses dois GNPAs sendo usados na escolha do pivô do Quicksort. Também comparamos essas duas versões probabilísticas como utras três implementações determinísticas que fizemos para o Quicksort. O intuito desse trabalho foi realizar uma análise experimental dessas variações do Quicksort usando GNPAs dando enfoque em analisar o comportamento da versão proposta em [KR93].

Abstract: We had studied in this work variations of Quicksort related with cache optimization and we hadrealized that worry about this topic makes the algorithm deeply limited and the resultant diferences are extremely specific and related with the choosen architeture. So we had studied variations of Quicksort which focus in modifying the way of choosing the pivot with the objective ofminimize the number of performed comparisions and changes. Among the looked variations,the probabilistic Quicksort caracterizes itself by using pseudo-random-numbers when choosing the pivot. So we had focused on study two random number genarator (RNG) algorithms, one by linear congruence [Knu00b] and another by five-way-independent [KR93]. We had analised, compared and tested these two RNGs beeing used on the pivot choice in Quicksort. We had alsocompared these two probabilistic versions with other three deterministic versions we had madefor Quicksort. The aim of this work was to perform an experimental analysis of these variations of Quicksort using RNGs and the main focus was to analise the behavior of the version proposedin [KR93].