Aps Dados Ciencia

APS 2012 3 SEMESTRE DE SISTEMA DE INFORMAÇAO

Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados

Ciência da Computação

NOME: Guilherme Rodrigues De Souza

RA: B057149

CAMPUS: Pinheiros 3° Semestre

DATA: 01/06/2012

ÍNDICE

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

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

Referencial Teórico..................................................................................................06

Desenvolvimento......................................................................................................07

Resultados e Discussão...........................................................................................12

Considerações Finais .............................................................................................13

Referências Bibliográficas.......................................................................................14

Código Fonte............................................................................................................16

OBJETIVO DO TRABALHO

Objetivo do trabalho é nos mostra o conceito e os tipos de ordenação de dados. Alguns são mais conhecidos como Quicksort ele é um método muito rápido e eficiente seu modo de ordenação é conhecido como divisão e conquista modo que as chave “menores” precedam as chaves “maiores” assimé coloca em ordem as duas sublistas de chaves menores e maiores recursivamente ate que se encontre. Também tem o radix sort e um algoritmo de ordenação rápido também estável pode se usado como ordenação de identificação de chave única é cada chave é uma cadeia de característica ou também pode se um numeral.

Também achamos o bubble sort e um algoritmo de ordenação mais simples ele percorrer o vector diversas vezes e vai subindo o maior dos elementos da seqüência até chega ao final. Esses são alguns dos ordenadores de dados que acha fácil na internet. O trabalho mostrou alguns ordenação de dados e os mais eficazes para cada elemento trabalhado. E mostrado no trabalho e também mostra diferencia de cada ordenação trabalhada aos logo do século.

A ordenação de dados e um conjunto amplo de algoritmos para realizar uma mesma tarefa, cada um deles com uma vantagem em particular sobre os outros, dependendo da aplicação e o algoritmos.

INTRODUÇÃO

Algoritmos de ordenação: Algoritmo e uma sequencia finita de instruções o sejam bem definidas e não ambíguas é cada tipo dela e executada em um período de tempo finito e com quantidade é esforço finito. Ordenação é um jeito de coloca um elemento em ordenação o seja seqüência de dados, ou informação. Também tem um termo técnico para ordenação é sorting, já a tradução literária é “classificação.

Tem diverso tipo de ordenação de dados o mais conhecido. Vou cita os mais achando na Internet como o Quicksort Método proposto por Charles Antony Richard Hoare em 1962, considerado como o mais rápido entre os principais métodos de ordenação. A idéia por trás doalgoritmo é escolher um valor "médio" (o valor do meio, também chamado pivô, que pode não corresponder exatamente ao valor do meio do vetor, depois de este estar ordenado) do vetor, passar todos os valores maiores do que ele para frente e todos os menores para trás. Ficamos então com o vetor dividido em duas partes, uma tem todos os valores menores que o valor escolhido, a outra tem todos os valores maiores que o valor escolhido. Aplicamos agora o algoritmo a cada uma das partes.

O processo é repetido até atingirmos partes de tamanho um. E também o mais achado na internet é o Bubble Sort (“Bolha”) Por ser simples e fácil de entender e programar, o Bubble Sort está entre os mais conhecidos algoritmos de ordenação. Porém, devido a sua baixa eficiência, devemos tratá-lo como uma solução mais para desenvolvimento de raciocínio que de uso recorrente (embora não seja um problema usá-lo em casos onde não se exige muito desempenho, como quando desejamos ordenar um conjunto com poucos elementos.). Seu princípio é a comparação e troca de valores entre posições consecutivas, fazendo com que os valores mais altos (ou mais baixos) migrem ("borbulhem") para o final do vetor a ser ordenado.

O Bubble sort é um algoritmo de ordenação de dados simples, que pode ser considerado extremamente lento, devido sua lógica de ordenação.

Sua estrutura baseia-se na lógica de comparação. Imagine um vetor, onde todos os dados encontram-se desordenados.

No primeiro passo deste algoritmo, verifica-se se o valor da posição 0 do vetor, é maior do que o valor de sua próxima posição: 1.

Em caso afirmativo, trocam-se suas posições, de modo que omaior valor fique sempre na última posição do vetor. Em caso afirmativo, trocam-se suas posições, de modo que o maior valor fique sempre na última posição do vetor.

Com a finalização desta primeira etapa de ordenação, efetua-se uma nova comparação e neste caso, utilizam-se as próximas posições do vetor: 1 e 2.

Com base neste sistema, podemos notar que o maior valor do vetor será deslocado até sua última posição. Podemos dizer que a cada tipo de ordenação de dados que e achado na internet e livros e fácil dizer que uso dele para ordena dado se usado em diversa área.

REFERENCIAL TEÓRICO

Radix sort e uns algoritmos de ordenação vistos até agora operam por comparação entre chaves. Qualquer ordenação por comparação deve efetuar Ω (n log n) comparações no pior caso.

O algoritmo RADIX SORT não opera por comparação como todos os algoritmos de

Ordenação vista até agora e que têm limite inferior Ω(n log n).

Radix Sort trabalha ordenando primeiro sobre o dígito menos significativo (da direita para a esquerda) e depois os mais