Algoritmo de ordenação

FACULDADE INTEGRADA PAULISTA
Redes de computadores

ALGORITMO DE ORDENAÇÃO

Nilson Pepe 210.119.015

São Paulo 20 de ABRIL de 2011

FACULDADE INTEGRADA PAULISTA
Redes de computadores

Algoritmo de ordenação

Professor: ZIROLDO Matéria: PROGRAMAÇÃO

São Paulo 20 de ABRIL de 2011

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 uncionamento em paralelo destes algoritmos, cujo objetivo é diminuir consideravelmente o tempo de execução dos mesmos.
Neste texto vamos abordar vários algoritmos de ordenação. Relativamente aos que realizam operações de comparação e troca, descrevemos o bubble sort, quicksort e hyperquicksort, mergesort. Também falamos sobre o rank sort e o counting sort, que não recorrem a este tipo de operações. No que diz respeito a algoritmos que obtêm uma performance muito superior quando paralelizados,vamos descrever o radix sort.
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem -- em outras