Algoritmo de ordenação
Introdução
• Algoritmos de Ordenação!? • Em vários momentos do dia a dia, o homem depara-se
com a necessidade de consultar dados ordenados. Como exemplo, pode-se citar uma lista telefônica. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Por isso uma das atividades mais utilizada na computação é a ordenação.
Introdução
• Existem diversos algoritmos para ordenação interna: • BubbleSort • InsertSort • SelectSort
• ShellSort
• QuickSort • HeapSort
• MergeSort
Definição de Ordenação
• Ordenar corresponde ao processo de rearranjar um
conjunto de objetos em ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado.
• Os métodos de ordenação são classificados em dois
grandes grupos:
• Ordenação interna e externa.
Classificação
• Ordenação
Interna: São os métodos que não necessitam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador;
• Ordenação Externa: Quando o arquivo a ser ordenado
não cabe na memória principal e, por isso, tem de ser armazenado em disco.
• OBS: A principal diferença entre os dois grupos é que no
método de ordenação interna qualquer registro p o de ser acessado diretamente, enquanto no método externo é necessário fazer o acesso em blocos
Análise de Algoritmos
• Cada algoritmo apresenta uma ordem de complexidade
que permite sua execução com um maior ou menor tempo/uso computacional.
• Classificamos o desempenho desses algoritmos nos
melhores e piores casos usando funções matemáticas e denominamos de ordem de complexidade, Grande-O ou notação assimptótica.
Análise de Algoritmos
• Naturalmente, é
possível determiná-lo através de métodos empíricos, isto é, obter o tempo de execução através da execução propriamente dita do algoritmo,