APS UNIP

Universidade Paulista

Ciência da computação

Atividade Prática Supervisionada

ALGORÍTMOS DE ORDENAÇÃO DE DADOS

Lucas Leal R.A.- C1423H-6

Vitor de Aguiar Baldini F. da Costa R.A.- C07717-8

Diego Astolphi R.A.- C07DCJ-0

Bauru

2015

Sumário

1. Objetivo do Trabalho .............................................................................. 03

⦁ Introdução .............................................................................................. 04

⦁ Algoritmos de ordenação ..................................................................... 05

⦁ Código Fonte .......................................................................................... 15

⦁ Referências Bibliográficas .................................................................. 20

⦁ Ficha de APS ........................................................................................ __

1. Objetivo do Trabalho

⦁ O objetivo do trabalho envolve conhecer os algoritmos Algoritmo de ordenação, como Bubble sort, Insertion sort, Quick sort, Selection sort entre outros e elaborar uma pesquisa sobre eles. Nas pesquisas, deverão ser expostas as ideias e teorias, além de uma discussão sobre os métodos usados por cada um. Após a discussão, cada grupo de trabalho deverá construir um programa com três, das estruturas estudadas. A linguagem escolhida para o desenvolvimento do trabalho é linguagem Java.

2. Introdução

Ao longo deste trabalho, serão expostos os algoritmos de ordenação : Bubble sort, Insertion sort, Shell sort, Selection sort. Será analisado seu código fonte, explicando sua função e mostrando o mesmo em diversas linguagem. Ao final do trabalho será elaborado um programa usando os algoritmos Bubble sort e Insertion sort.

Ordenação consiste ao método de reorganizar um conjunto de objetos em ordem crescente ou decrescente comparando os elementos para determinar qual deles vem em primeira ordem na lista ordenada, tendo como objetivo facilitar a recuperação de itens de um determinado conjunto.

Existem muitos algoritmos de ordenação, a escolha mais eficiente vai depender de vários fatores, tais como: número de itens a ser classificado; se os valores já estão agrupados em subconjuntos ordenados etc.

Atualmente há uma grande necessidade de guardar informações e possuí-las ordenadas, seja por ordem alfabética, por idade, localidade entre outros.

3. Algoritmos de ordenação

Este capítulo abordará os algoritmos de ordenação Bubble sort, Insertion sort, Shell sort, Selection sort.

3.1 Bubble sort.

O algoritmo de ordenação bubble sort usa uma estratégia de “comparação e troca” que é aplicada em várias iterações sobre os dados a ser ordenados. Passo a explicar os passos do algoritmo sequencial. Partindo do principio que se deseja ordenar (de forma crescente) um vector de números nas seguintes posições: x0, x1,…, xn-1, xn.

O algoritmo começa por comparar o número que se encontra na posição x0 com

o da posição x1, e troca (quando necessário) os números de maneira a ficar

o maior dos dois na posição x1. De seguida, repete o mesmo procedimento para as posições x1 e x2, onde na posição x2 ficará o maior dos números que se encontra nas posições x1 e x2. Este processo é repetido de forma análoga até chegar à comparação entre as posições xn-1 e xn. Este processo anterior de comparações e trocas será considerado uma fase do algoritmo, sendo o algoritmo bubble sort constituído (na pior das hipóteses) por n-1 fases semelhantes à anterior.

O descrito anterior é o Bubble sort sequencial, podemos melhor ele através da técnica de pipelining (paralelo) é possível melhorar o desempenho do algoritmo, em

comparação com a versão sequencial. Isto se deve ao facto de ser possível serem

executadas várias fases em simultâneo na versão com pipelining. É possível tal método, pois como cada fase só faz uma comparação por cada par de posições, quando a primeira fase se encontra na comparação entre as posições x2 e x3, a segunda fase já pode (sem problema algum) fazer a comparação entre as posições x0 e x1. A terceira fase terá início quando a segunda fase estiver a

comparar as posições x2 e x3, e a primeira ase, por sua vez, se encontrar na

comparação das posições x4 e x5.

3.2 Insertion sort

Insertsort é um método de ordenação flexível, muito eficiente quando se utiliza um vetor com poucos elementos. Esse método considera um elemento um a um, a partir de i=2, inserindo o i-ésimo item da sequência em seu lugar entre os elementos já tratados. Um exemplo deste algoritmo e ordenar cartas de um baralho, ele pega o elemento em consideração e o insere movendo o elemento