PARALELIZAÇÃO DO ALGORITMO QUICK-SORT MULTI-PIVOT COM A UTILIZAÇÃO DE THREADS

Resumo

Organizar dados é um problema recorrente na Computação, pois muitas aplicações possuem uma grande quantidade de dados e a tendência, se os dados não forem previamente organizados, é a de que seja necessário um grande esforço computacional para encontrar os dados desejados. A fim de agilizar a procura e obter um bom desempenho foram criados os algoritmos de ordenação. Existe uma grande variedade destes algoritmos, tais como Bubble-sort, Merge-sort, Selection-sort e Insertion-Sort. No entanto, neste artigo, iremos tratar sobre o algoritmo Quick-Sort, por este ser um dos mais eficientes (em termos de tempo de ordenamento) em meio ao rol de algoritmos já propostos. Existem muitas variações do algoritmo Quick-Sort, a mais simples é o single-pivot, onde a ordenação ocorre com a utilização de apenas um pivô (elemento usado para auxiliar no processo de ordenamento). Com o tempo, outras implementações baseadas nesta solução mais simples de Quick-sort também se tornaram disponíveis, tais como o Quick-sort dual-pivot e multi-pivot. O algoritmo Quick-sort é conhecido como um dos mais rápidos, porém, estudos demonstraram que um dual-pivot tende a ordenar mais rapidamente um conjunto de dados, sugerindo que o aumento na de pivôs contribui para um melhor desempenho do algoritmo clássico Quick-sort. Tendo em vista a velocidade da ordenação, a proposta deste trabalho é melhorar o tempo de execução de um Quick-sort multi-pivot, por meio de uma implementação utilizando múltiplas threads. Para isso, a estratégia central consiste em dividir o conjunto de dados a ser ordenado (vetor) em vários blocos com menos elementos para que sejam ordenados simultaneamente. No método utilizado foram feitos ordenamentos paralelos utilizando threads, na medida que as threads ordenavam suas partes, o vetor era novamente dividido em menor número de threads que na fase anterior, até chegar na thread final que irá deixar o vetor completamente ordenado. Como resultado obtivemos que ao separar o vetor em quatro partes, depois duas e após isso, a thread final, percebeu-se que foi o mais eficiente quick-sort dual pivot com paralelismo.