OS ALGORITIMOS DO ORDENAÇÃO

UNIVERSIDADE ESTÁCIO DE SÁ - RJ

CAMPUS NOVA IGUAÇU

CURSO DE SISTEMAS DE INFORMAÇÃO

JORDANE MAURELLI GARCIA

MAYCON BRUNO MONTES GOMES CONSTANCIO

ALGORITIMOS DO ORDENAÇÃO

Rio de Janeiro - RJ

05/2020

 INSERTION SORT E COMB SORT

Trabalho de Estudo Dirigido apresentado ao Prof. Ronaldo Candido dos Santos na Universidade Estácio de Sá – Campus Nova Iguaçu como requisito para aprovação na disciplina algoritmos avançados do curso de sistemas de informação.

        

Rio de Janeiro - RJ

05/2020

SUMÁRIO

1. Introdução .....................................................................................................	03
2. Justificativa ....................................................................................................	04
3. Objetivos ........................................................................................................	05
4. Metodologia ....................................................................................................	06
5. Resultados obtidos .........................................................................................	07
6. Conclusão ......................................................................................................	19
7. Referências Bibliográficas .............................................................................	20

        

1. Introdução[pic 1]

Esse trabalho irá apresentar resultados de uma pesquisa sobre métodos de ordenação, a qual possuem técnicas de ordenação diferentes para resolver uma mesma tarefa. Cada aplicação possui sua complexidade, e cada algoritmo tem sua particularidade, vantagem e desvantagem sobre outro algoritmo.

---

1. Justificativa

        As operações de ordenação de dados são de suma importância para sistemas computacionais, dentro do contexto da programação, o uso do algoritmo com maior eficácia tem um grande impacto no desempenho de uma determinada aplicação, e o objetivo dessa pesquisa é exporá exemplos de algoritmos e sua real aplicação dentro de sistema e sua utilização, otimizando o tempo de execução e utilização.

---

1. Objetivos

Em nosso trabalho, iremos abordar o uso de dois algoritmos de ordenação, nos nossos exemplos iremos utilizar o Insertion Sort e o Comb Sort, assim como sua implementação, e o uso do código. Analisaremos o código tanto na prática, como na teoria, com exemplos e definições.

---

1. Metodologia

Imagine como seria buscar um número em um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética? Seria muito complicado. A ordenação ou classificação de registros consiste em organizá-los em ordem crescente ou decrescente e assim facilitar a recuperação desses dados. A ordenação tem como objetivo facilitar as buscas e pesquisas de ocorrências de determinado elemento em um conjunto ordenado.

Na computação existe uma série de algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados, eles são conhecidos como Métodos de Ordenação ou Algoritmos de Ordenação. Vamos conhecer um pouco mais sobre eles.

Os métodos de ordenação se classificam em:

Ordenação Interna: Onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.

Ordenação Externa: Onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos.

Dentro da ordenação interna temos os Métodos Simples e os Métodos Eficientes.

Métodos Simples: Os métodos simples são adequados para pequenos vetores, são programas pequenos e fáceis de entender. Possuem complexidade C(n) = O(n²), ou seja, requerem O(n²) comparações. Exemplos: Insertion Sort, Selection Sort, Bubble Sort, Comb Sort.

Métodos Eficientes: Os métodos eficientes são mais complexos nos detalhes, requerem um número menor de comparações. São projetados para trabalhar com uma quantidade maior de dados e possuem complexidade C(n) = O(n log n). Exemplos: Quick sort, Merge sort, Shell sort, Heap sort, Radix sort, Gnome sort, Count sort, Bucket sort, Cocktail sort, Timsort.

        

---

1. Resultados obtidos

Insertion Sort

O Insertion Sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.

O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer. Confira o exemplo a seguir:

0	1	2	3	4
5	3 chave	1	2	4

A chave (3) está na posição 1 (segunda posição) da lista, pois não há ninguém a se comparar se pegássemos o primeiro item da lista. Então consideramos que o primeiro elemento da lista (5) já esteja ordenado.