Algoritmo de ordenação

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2433 palavras )
  • Download(s) : 0
  • Publicado : 27 de maio de 2011
Ler documento completo
Amostra do texto
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ÇÃOSã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ímosque, 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 normalmentedemoram 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 outraspalavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.
Métodos simples
Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termosgerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.
O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor dovetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada passagemfazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.No melhor caso, o algoritmo executa n2 / 2 operações relevantes, onde n representa o número de elementos do vector. No pior caso, são feitas 2n2 operações. No caso médio, são feitas 5n2 / 2 operações. Acomplexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.O algoritmo pode ser descrito em pseudo-código como segue abaixo. V é um VECTOR de elementos que podem ser comparados e n é o tamanho desse vector.
O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente[1]) é um algoritmo de...
tracking img