Clique para abrir a versão em Português
Bem-vindo ao repositório Parallel Sortings! Este projeto explora o poder da programação paralela por meio de algoritmos de ordenação seriais e paralelos implementados em Java (atualmente) e C++ (em breve). Nosso objetivo é ilustrar como o paralelismo de tarefas pode otimizar significativamente o desempenho, especialmente para grandes conjuntos de dados.
Este repositório faz parte de um projeto universitário que introduz e demonstra a eficácia da programação paralela. Ao dividir as tarefas de ordenação e processá-las simultaneamente, buscamos alcançar resultados mais rápidos do que as abordagens seriais tradicionais.
Este projeto demonstra:
- Algoritmos de ordenação seriais para comparações de referência.
- Algoritmos de ordenação paralelos para destacar os ganhos de desempenho por meio da divisão de tarefas.
- Métricas de desempenho com diferentes tamanhos de conjuntos de dados para ilustrar a escalabilidade.
Nossa solução em Java implementa e avalia o desempenho de vários algoritmos de ordenação seriais e paralelos com diferentes tamanhos de arrays para comparar os tempos de execução.
-
Algoritmos de Ordenação Seriais:
- Merge Sort (Ordenação por Intercalação)
- Bubble Sort (Ordenação por Bolha)
- Quick Sort (Ordenação Rápida)
- Selection Sort (Ordenação por Seleção)
- Insertion Sort (Ordenação por Inserção)
- Counting Sort (Ordenação por Contagem)
-
Algoritmos de Ordenação Paralelos:
- Parallel Merge Sort (Ordenação por Intercalação Paralela)
- Parallel Bubble Sort (Ordenação por Bolha Paralela)
- Parallel Quick Sort (Ordenação Rápida Paralela)
- Parallel Selection Sort (Ordenação por Seleção Paralela)
- Parallel Insertion Sort (Ordenação por Inserção Paralela)
- Parallel Counting Sort (Ordenação por Contagem Paralela)
Abaixo estão alguns tempos de execução para cada algoritmo com tamanhos de arrays de 10, 100, 1.000 e 10.000 elementos. Os resultados ilustram os benefícios da ordenação paralela à medida que os tamanhos dos arrays aumentam.
Clique para expandir os resultados do benchmark
- Ordenações Paralelas:
- Tempo do Parallel Merge Sort: 11.970.428 ns
- Tempo do Parallel Bubble Sort: 8.507.228 ns
- Tempo do Parallel Quick Sort: 1.919.143 ns
- Tempo do Parallel Selection Sort: 2.754.165 ns
- Tempo do Parallel Insertion Sort: 7.078.392 ns
- Tempo do Parallel Counting Sort: 6.335.696 ns
- Ordenações Seriais:
- Tempo do Serial Merge Sort: 649.523 ns
- Tempo do Serial Bubble Sort: 6.842 ns
- Tempo do Serial Quick Sort: 241.581 ns
- Tempo do Serial Selection Sort: 5.233 ns
- Tempo do Serial Insertion Sort: 7.125 ns
- Tempo do Serial Counting Sort: 35.799 ns
... (e assim por diante para tamanhos maiores de arrays)
A versão em C++ dos algoritmos de ordenação será introduzida para explorar ainda mais otimizações de desempenho na programação paralela. Esta versão irá:
- Usar o XMake como sistema de build.
- Incluir algoritmos de ordenação seriais e paralelos semelhantes para comparação direta com a implementação em Java.
- Medir o desempenho com diferentes tamanhos de dados para comparar a eficiência do C++ vs. Java nas tarefas de ordenação paralela.
- Comparação entre Linguagens: Após a implementação em C++, vamos analisar e comparar os resultados de desempenho entre Java e C++. Isso proporcionará insights sobre como as diferenças entre as linguagens e seus ambientes de execução afetam o desempenho de algoritmos paralelos.
- Testes de Escalabilidade: Com conjuntos de dados maiores, nosso objetivo é observar como os algoritmos se comportam com cargas de trabalho crescentes e determinar os pontos de equilíbrio para os benefícios da paralelização.
Para rodar a implementação em Java:
- Compile os arquivos Java:
javac *.java - Execute a classe principal:
java MainClass - Veja a saída do benchmark no console, conforme os resultados de exemplo mostrados acima.
Para o código C++ que será disponibilizado:
- Clone o repositório e instale o XMake caso necessário.
- Compile e execute o programa usando:
xmake xmake run
Click to open the English version
Welcome to the Parallel Sortings repository! This project explores the power of parallel programming through serial and parallel sorting algorithms implemented in Java (current) and C++ (coming soon). Our aim is to illustrate how task parallelism can significantly optimize performance, particularly for large datasets.
This repository is part of a college project that introduces and demonstrates the effectiveness of parallel programming. By breaking down sorting tasks and processing them simultaneously, we aim to achieve faster results than traditional serial approaches.
This project showcases:
- Serial sorting algorithms for baseline comparisons.
- Parallel sorting algorithms to highlight performance gains via task division.
- Performance metrics across varying dataset sizes to illustrate scalability.
Our Java solution implements and benchmarks various serial and parallel sorting algorithms with different array sizes to compare execution times.
-
Serial Sorting Algorithms:
- Merge Sort
- Bubble Sort
- Quick Sort
- Selection Sort
- Insertion Sort
- Counting Sort
-
Parallel Sorting Algorithms:
- Parallel Merge Sort
- Parallel Bubble Sort
- Parallel Quick Sort
- Parallel Selection Sort
- Parallel Insertion Sort
- Parallel Counting Sort
Below are sample timings for each algorithm based on array sizes of 10, 100, 1,000, and 10,000 elements. Results illustrate the benefits of parallel sorting as array sizes increase.
Click to expand benchmark results
- Parallel Sorts:
- Parallel Merge Sort Time: 11,970,428 ns
- Parallel Bubble Sort Time: 8,507,228 ns
- Parallel Quick Sort Time: 1,919,143 ns
- Parallel Selection Sort Time: 2,754,165 ns
- Parallel Insertion Sort Time: 7,078,392 ns
- Parallel Counting Sort Time: 6,335,696 ns
- Serial Sorts:
- Serial Merge Sort Time: 649,523 ns
- Serial Bubble Sort Time: 6,842 ns
- Serial Quick Sort Time: 241,581 ns
- Serial Selection Sort Time: 5,233 ns
- Serial Insertion Sort Time: 7,125 ns
- Serial Counting Sort Time: 35,799 ns
... (and so forth for larger array sizes)
The C++ version of the sorting algorithms will be introduced to further explore performance optimizations in parallel programming. This version will:
- Use XMake as the build system.
- Include similar serial and parallel sorting algorithms for direct comparison with the Java implementation.
- Measure performance across varying data sizes to compare the efficiency of C++ vs. Java in parallel sorting tasks.
- Cross-Language Comparison: After the C++ implementation, we’ll analyze and compare performance results across Java and C++. This will provide insights into how language and runtime differences affect parallel algorithm performance.
- Scalability Testing: With larger data sets, we aim to observe how the algorithms perform under increasing workloads and determine the break-even points for parallelization benefits.
To run the Java implementation:
- Compile the Java files:
javac *.java - Run the main class:
java MainClass - View the benchmark output in the console, as shown in the sample results above.
For the upcoming C++ code:
- Clone the repository and install XMake if necessary.
- Compile and execute the program using:
xmake xmake run