O Desenvolvimento De Sistema Para Análise De Performance De Algoritmos De Ordenação De Dados

[pic 1]

Av. Alberto Benassi, 200 - Parque das Laranjeiras - Araraquara - SP
CEP 14804-300 - Tel.: (16) 3336-1800

DP DE ATIVIDADES PRÁTICAS SUPERVISIONADAS

“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS”

REFERENTE AO SEMESTRE 4°

                                               Fernando de Melo Perroti C272248 08/TT8P52

__________________________________________________________________________________________

4° Semestre Ciência da Computação (CC)

____________________________________________________________________________________

__________________________________________________________________________________________

     Trabalho apresentado à

 UNIP-Campus Araraquara

vinculado à DP de Estudos Disciplinares,

como parte dos requisitos  para    avaliação semestral, no Curso de Ciência da Computação.

Araraquara/- 2023

Índice

Introdução

Objetivo do Trabalho

Referencial Teórico

Desenvolvimento

Resultados e Discussão

Considerações Finais

Referências Bibliográficas

Ficha de Atividades Práticas Supervisionadas

Introdução

1 Ordenação

Importância da Ordenação

Terminologia básica Eficiência

2 Tipos de Ordenação

Ordenação por Troca

Ordenação por Seleção

Ordenação por Inserção

3 Outros Tipos de Ordenação

Ordenação de Shell e por Cálculo de Endereços

Ordenação por Intercalação e por Contagem de Menores

Ordenação por Contagem de Tipos e de raízes

Definição de Ordenação: Tornar mais simples, rápida e viável a recuperação de uma determinada informação, num conjunto grande de informações.

Observações sobre os métodos:

1. Shellsort, quicksort e heapsort têm a mesma ordem de grandeza para arranjos de até 30 mil elementos

2. O quicksort é o mais rápido para todos os tamanhos aleatórios experimentados

3. A relação heapsort/quicksort se mantém constante para todos os tamanhos de entrada

4. A relação shellsort/quicksort aumenta com o tamanho da entrada

5. Para arquivos pequenos (500 elementos), o shellsort é mais rápido que o heapsort (e vice versa)

6. Inserção é o método mais rápido para qualquer tamanho se os elementos estão ordenados (e vice versa)

7. Entre os algoritmos de custo quadrático, o inserção é melhor para entradas aleatórias

Cada um desses métodos coloca os elementos de uma determinada sequência para concluir sua ordenação. Isso possibilita acesso de dados de modo mais rápido.

Bubble Sort: Método mais intuitivo e simples de ser implementado, mas parece ser o menos eficiente de todos.

Selection Sort: Este tipo de ordenação seleciona o menor elemento do subvetor não ordenado e troca com o primeiro elemento deste subvetor.

Quick Sort: É um algoritmo de ordenação considerado entre os mais rápidos e eficientes.

Objetivo do Trabalho

Realizar um trabalho utilizando algoritmos considerando o seguinte exemplo: o geoprocessamento de imagens da floresta amazônica permite a fiscalização de ações de crimes ambientais. Os satélites geram cerca de 100 mil imagens de toda a região a cada 24 horas, essas imagens são armazenadas o catalogadas.

Selecionar três ou mais técnicas e desenvolver um sistema computacional completo que obtenha os dados catalogados das imagens capturadas dos satélites, efetue a ordenação e compare os desempenhos entre eles. A unidade de medida para efeito de comparação deverá ser o tempo total de ordenação. Não deverá ser contabilizado o tempo de aquisição dos dados, apenas o processo específico de ordenação.

Referencial Teórico

Bubble Sort

Bubble sort é um algoritmo de classificação simples e bem conhecido. É usado na prática uma vez em uma lua azul e sua principal aplicação é fazer uma introdução aos algoritmos de classificação. O bubble sort pertence aos algoritmos de classificação O(n2), o que o torna bastante ineficiente para classificar grandes volumes de dados. O bubble sort é estável e adaptativo.

Algoritmo

1. Compare cada par de elementos adjacentes desde o início de uma matriz e, se estiverem em ordem inversa, troque-os.
2. Se pelo menos uma troca tiver sido feita, repita a etapa 1.

Você pode imaginar que a cada passo grandes bolhas flutuam para a superfície e permanecem lá. Na etapa, quando nenhuma bolha se move, a classificação pára. Vejamos um exemplo de classificação de uma matriz para tornar a ideia de bubble sort mais clara.

Exemplo. Classifique {5, 1, 12, -5, 16} usando a classificação por bolha.

[pic 2]

Análise de complexidade

A complexidade média e do pior caso do bubble sort é O(n2). Além disso, faz trocas O(n2) no pior dos casos. O bubble sort é adaptativo. Isso significa que, para a matriz quase classificada, ela fornece a estimativa O(n). Evite implementações, que não verificam se o array já está classificado em cada etapa (quaisquer trocas feitas). Essa verificação é necessária, a fim de preservar a propriedade adaptativa.

...