Estudo sobre métodos de Ordenação

Páginas: 13 (3018 palavras) Publicado: 18 de setembro de 2014
´
UM ESTUDO SOBRE METODOS DE ORDENACAO
¸˜
Aluno: Gustavo Silva Melo
Orientador: Michel Pires Silva

Resumo
Tem-se como objetivo deste artigo apresentar um estudo sobre os m´todos de ordena¸ao
e

mais aplic´veis em literatura. Busca-se com isso descobrir qual dos m´todos avaliados aprea
e
senta melhor efic´cia para diferentes conjuntos de dados. Para tanto, os estudos aqui apresenatados foram feitos utilizando arquivos de texto e o desenvolvimento foi realizado na linguagem
Pascal. Foi feita a ordena¸˜o dos arquivos em ordem alfab´tica e feita a medi¸˜o dos tempos
ca
e
ca
de execu¸ao de cada m´todo, para tamanhos diferentes de dados. Os arquivos utilizados no

e
estudo, variaram de vinte a dez milh˜es de palavras.
o

1. Introdu¸˜o
ca
Um problema comum emcomputa¸ao ´ o de ordenar conjuntos de dados. Esse problema,
c˜ e
na atualidade, tem se tornado inerente nas mais diversas areas da computa¸˜o e afins. Nesse
´
ca
contexto, de forma a resolvˆ-lo tem-se em literatura v´rios algor´
e
a
ıtimos cujo objetivo ´ prover
e
meios para ordenar tais conjuntos. Esses algor´
ıtimos definem vantagens e desvantagens em
seu processo de execu¸˜o. Sabendo-sedisso, tem-se neste trabalho um estudo dos m´todos e
ca
e
algor´
ıtimos mais conceituados encontrados em literatura.

1.1. Selection Sort
De acordo com [Ziv11], o selection sort ´ considerado um dos algor´
e
ıtimos de ordena¸˜o
ca
mais simples cujo funcionamento consiste em selecionar o menor item do vetor, e a seguir
troc´-lo com o item que est´ ocupando a primeira posi¸ao. Repete-se aopera¸ao com os
a
a


n − 1 itens restante, em seguida com n − 2 itens, at´ que reste apenas um elemento.
e
1.2. Insertion Sort
J´ o m´todo insertion sort funciona de maneira similar ao anterior, por´m com melhorias
a
e
e
em quest˜o de tempo de execu¸ao. Sendo muita das vezes comparadas ao modo como se
a

ordenam cartas em um jogo de pˆquer, como cita [THCS02]. Pegando cadaitem, e inserindo
o
na posi¸ao correta no vetor. Para encontrar essa posi¸ao correta, comparamos o item a ser


ordenado a cada um do vetor, come¸ando do final at´ a primeira posi¸˜o. Encontrado um
c
e
ca
valor maior do que o item a ser ordenado, ´ inserido o item na posi¸˜o desejada no vetor.
e
ca
1.3. Shell Sort
O algor´
ıtimo proposto por Donald Shell em 1959, trabalha como umaextens˜o do m´todo
a
e
insertion sort. Tal algor´
ıtimo tira proveito que o mesmo funciona bem em sequˆncias pequenas
e
e quase ordenadas. Sua id´ia ´ ver o vetor dos n´meros a ser ordenados como v´rias listas
e e
u
a
Centro Universit´rio de Formiga
a

12 de junho de 2013

interligadas com um distancia h entre os elementos pr´ximos de certa sequˆncia. O algor´
o
e
ıtimopr´-ordena todos os elementos de todas as sublistas a uma distˆncia h, repetindo o processo
e
a
que ir´ diminuir a quantidade de sublistas, aumentando o tamanho delas. Dessa forma,
a
a distˆncia h ´ decrescida, chegando na ultima passada do la¸o (h = 1). A partir da´
a
e
´
c
ı,
corresponde ao m´todo de inser¸ao, por´m nenhum dos itens necessita ser movido para
e

e
posi¸oes largamentedistantes. [dSdS10]

1.4. Merge Sort
´
E um m´todo particular de ordena¸˜o que aplica a id´ia ‘divis˜o e conquista’. Trabalha
e
ca
e
a
ıvel, tamb´m divide
e
dividindo o vetor em duas partes(sub-vetores) de tamanho n (se poss´
2
os sub-vetores). O trabalho ´ feito repetidamente para ordenar partes menores e fazer o
e
jun¸ao(merge) dos mesmos, at´ obter um vetor ordenado completo. Aordena¸ao e feita

e

usando recursividade. Foi criado em 1945 pelo matem´tico John Von Neumann.
a
[Mel02b][dS13b]
1.5. Quick Sort
O quick sort ´ considerado o algor´
e
ıtimo de ordena¸ao interna m´is r´pido conhecido,

a a
aplic´vel a uma ampla variedade de situa¸˜es, sendo talvez mais usado que qualquer outro
a
co
algor´
ıtimo. Desenvolvido por C.A.R. Hoare em 1960, em...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Estudo dos Metodos de ORdenação
  • Métodos de Ordenação análise sobre os métodos
  • Resumo e Fichamento sobre Métodos de Estudo
  • Estudo teórico sobre os métodos sociátricos
  • Metodos de Ordenacao
  • Métodos de ordenação
  • Metodos de Ordenacao
  • métodos de ordenação

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!