Algoritmos de ordenação

UNIVERSIDADE PAULISTA

CIÊNCIAS DA COMPUTAÇÃO

NOME DOS ALUNOS

Renan Alves Oliveira de Almeida R.A: A497AH-3

José Pereira Filho R.A: A45008-4

Diogo Soares de Camargo R.A: A4815D0

ALGORITMOS DE ORDENAÇÃO

SOROCABA

2011

ÍNDICE

Resumo 3
Introdução 3
2 – Bubble Sort 3 2.1 Sequencial 4 2.2 Paralelo 5
3 – Merge Sort 5 3.1 Sequencial 6 3.2 Paralelo 7 3.3 Odd-Even merge sort 8
4 – Quicksort 8 4.1 Paralelo 10 4.2 Hyperquicksort 12
5 – Rank sort 14
6 – Counting sort 15
7 – Radix sort 16
8 – Conclusão 16
9 – Referências 18
10 – Linhas de código

Resumo Neste artigo são apresentados vários algoritmos de ordenação: bubble sort, mergesort, quicksort, hyperquicksort, rank sort, counting sort e radix sort. É feita uma descrição do seu funcionamento em série e em paralelo, fazendo-se referência a vantagens e desvantagens e problemas resultantes do seu uso. Concluímos que, na grande maioria dos casos, a implementação paralela dos algoritmos produz melhores resultados a nível de complexidade temporal que em série.

1 Introdução A ordenação é um dos aspectos fundamentais das ciências computacionais. Torna-se, então, importante reduzir ao máximo a complexidade temporal dos algoritmos que lidam com este problema. As melhores ordenações em série normalmente demoram O(n log n), tempo que tende a agravar com o aumento do número de elementos. Deste modo, foram desenvolvidas versões para funcionamento em paralelo destes