Algoritimos De Ordenação

ALGORITMOS DE ORDENAÇÃO

SELECTION SORT E QUICK SORT

RESUMO

Este artigo tem como apresentação a análise e comparação entre dois algoritmos de ordenação, o Selection sort (ordenação por seleção) e o quick Sort. Foram apresentadas suas aplicabilidades, bem como sua eficiência e forma usual de serem escritos. Também foi apontado de forma explicativa os motivos pelos quais diferem-se levando-se em consideração os apontamentos citados.

Palavras Chave: Algoritmo, Selection Sort, Quick Sort, Aplicabilidade.

INTRODUÇÃO

Desde o início dos tempos modernos dados e informações precisam ser manipulados e para facilitar tal manipulação, nas décadas mais recentes a Computação tem um papel importante na realização desse trabalho.

Nos dias de hoje uma grande quantidade de dados é gerada e mais do que antes precisam estar de forma organizada para que sejam obtidos melhores resultados, assim como realizar buscas de forma mais rápida e precisa na manipulação da informação.

A forma de organizar, ordenar tais dados é realizada através de algoritmos de Ordenação. Existem inúmeros tipos de algoritmos dessa natureza, cada um com suas vantagens e desvantagens, sua aplicabilidade específica, dependendo do resultado que se espera.

Este trabalho tem como finalidade apresentar os métodos de ordenação por seleção (utiliza-se do método de procurar o menor vetor e jogá-lo para a primeira posição) e o quick sort (tem por finalidade dividir um único problema em diversas partes, facilitando e agilizando a resolução dos mesmos), suas aplicabilidades, comparação na eficiência em tempo de resposta entre outros aspectos importantes dos mesmo na manipulação de dados. Como base realizamos pesquisas e reunimos materiais provenientes da internet, como artigos ciêntíficos, páginas especializadas no assunto abordado neste artigo, bem como literaturas escritas, todos com o intuito de entendermos e expormos de maneira mais exata como funcionam os dois algoritmos aqui estudados( quick sort e selection sort) ,a maneira como são aplicados e sua eficiência.

Estudantes da Faculdade de Tecnologia IBTA

Daniel Henrique de Lima, Analista de Suporte, cursando 2.Trimestre RC

Diego Silva do Nascimento, Analista de Suporte, cursando 2.Trimestre RC

Eduardo Rondina Santos, Analista Telecom, cursando 2.Trimestre RC

Luciano Fernandes Galindro, Auxiliar Financeiro, cursando 2.Trimestre RC

Valéria Aparecida Pinto Macedo, Analista de Sistemas, cursando 3.Trimestre BD

Quick Sort

Quando se trata de performance e velocidade, o Quick Sort é o mais rápido método de ordenação interna que se conhece. Ele foi inventado por C. A. R em 1960 na Universidade de Moscou como estudante tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente. A síntese era dividir um problema de ordenação com n itens em dois problemas menores. Os problemas menores são ordenados e depois são combinados para dar a solução.

A seguir os passos para a o método partição que possui o seguinte comportamento:

1) Escolha o valor de x.

2) Percorra o vetor a partir da esquerda até que A[i] ≥ x.

3) Percorra o vetor a partir da direita até que A[j] ≤ x.

4) Troque A[i] com A[j].

5) Repita o processo até os apontadores i e j se cruzarem.

Ao final, o vetor A[Esq..Dir] está particionado de tal forma que:

Os itens em A[Esq], A[Esq + 1], ..., A[j] são menores ou iguais a x;

Os itens em A[i], A[i + 1], ..., A[Dir] são maiores ou iguais a x.

Abaixo o pseudo código para o entendimento do método partição:

Partição (A, p, r)

1 x ← A[p]

2 i ← p−1

3 j ← r+1

4 enquanto 0 = 0 faça

5 repita j ← j−1

6 até que A[j] ≤ x

7 repita i ← i+1

8 até que A[i] ≥ x

9 se i < j

10 então troque A[i] ↔ A[j]

11 senão devolva j

A partição consiste em incrementar um apontador e comparar um item do vetor contra um valor fixo em x. Essa razão da velocidade do Quick Sort.

Abaixo o Algoritmo Quick Sort (Implementação Simples/) que tem como base a estratégia da divisão e conquista. O método é chamado recursivamente. Podemos ver um exemplo de acordo com o autor ZIVIANI:

Quick sort (tipoInfo : a[], inteiro : esq, dir)

inteiro i;

início

se dir > esq então

i <- particione(a, esq, dir);

quicksort(a, esq, i-1);

quicksort(a, i+1, dir);

fim se

fim

(ZIVIANI, NIVIO, 2007 p 111-114)

Vantagens e Desvantagens

Vantagens

É extremamente eficiente para ordenar arquivos de dados. Necessita