APS Ciencia da Computacao 2 ano 3 semestre

...

O presente trabalho acadêmico apresenta, conforme citado acima, uma possibilidade de aplicação de seus métodos de ordenação junto a empresas, e porque não residências e repartições públicas, no intuito de contribuir para organização e ordenação de dados, visando economia de energia elétrica como uma hipótese de seus vários destinos flexíveis. Porém, conforme solicitado, o objetivo principal do trabalho não se destina a aprofundar-se nessa questão, mas sim de entender e avaliar os diversos métodos de ordenação de dados no sentido de contribuir com constatações referente a comparação entre eles. Dessa forma, os autores desse trabalho exaltam a grandeza do ser humano de ter a sua disposição funções computacionais que possibilitem um melhor desenvolvimento e manutenção de questões ambientais e de sustentabilidade através da oferta de informação que facilite a tomada de decisão por parte de seus responsáveis visando na melhoria dessas áreas. O Grupo espera que as conclusões aqui apresentadas possam contribuir com o conhecimento na área de ordenação de dados aos leitores de forma a atingir, consequentemente, a contribuição para o meio ambiente e desenvolvimento sustentável.

Um algoritmo que ordena um conjunto, geralmente representado num vetor, é chamado de algoritmo de ordenação. Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Entre os mais importantes, podemos citar bubble sort (ou ordenação por flutuação), heap sort (ou ordenação por heap), insertion sort (ou ordenação por inserção), merge sort (ou ordenação por mistura) e o quicksort. Existem diversos outros, que o aluno pode com dedicação pesquisar por si. Para estudo no entanto nos concentraremos em alguns dos quais são comuns: Selection sort, Bubble sort, Combsort e Insertion sort.

Para cada modelo computacional será gerado a mesma lista com os mesmos dados, calculando-se o tempo necessário para cada um dos algoritmos organizarem os itens de seus vetores, os quais poderão ter menos e/ou mais itens, com intuito de diferenciar a eficiencia em situações diversas.

O tempo, por razões quantitativas, será contabilizado em nanosegundos.

---------------------------------------------------------------

Referencial teórico

Método Bolha:

O método em questão realiza seu trabalho pelo princípio da ordenação por troca, ou seja, o método utiliza-se de uma metodologia muito intuitiva para organizar suas informações, que se dá através de varreduras, por todo o conjunto de dados, comparando o “dado da vez” com o seu sucessor, caso esse dado seja maior ou menor que o próximo (de acordo com o objetivo da ordenação) o método realiza a troca entre os dois colocando-os de forma ordenada entre si, a partir daí o próximo dado a ser analisado é o sucessor do “dado da vez” que, se foi alterado da última vez ou não, passará pelo mesmo processo de comparação com o seu sucessor. Porém o método bolha não se encerra por aí: Conforme já falado anteriormente, os números estão em situação ordenada em relação aos seus “vizinhos”, porém não em relação ao conjunto de dados, ou vetor, como um todo. Por isso é necessário que sejam feitas novas varreduras sobre as informações até que esse número de comparações completas no conjunto de dados seja igual ao número de elementos que o mesmo contém dentro de si.

O método bolha não é recomendado para grande quantidade de dados devido a grande ocorrência de comparações de dados e de sua dificuldade de leva um elemento por várias posições longe de onde inicialmente estava sem que muitas comparações sejam feitas ao invés de fazer isso com apenas uma troca e comparação. Por exemplo: o um elemento que originalmente encontrava-se em uma extremidade de um vetor e que deve ficar, em sua forma ordenada, na outra extremidade deve gastar um tempo considerável para todas as comparações e substituições até chegar ao seu destino.

Método por inserção:

O método por inserção visa a comparação de um elemento com todos os valores anteriores no conjunto de dados, ou vetor, com o intuito de inseri-lo no seu local correto, pelo menos em relação aos seus antecessores. Dessa forma, também como no método bolha, se deve varrer todos os dados da aplicação e comparar o número, ou dado da vez, com seus antecessores para decidir onde o mesmo deve ser inserido. Sendo assim, o método deve analisar um dado externo ou a cópias de um dado interno com os dados disponíveis em seu arquivo principal para decidir onde inseri-lo.

O método analisa se o número, por exemplo, inteiro é menor que seu antecessor, caso seja, ele insere o número “da vez” no lugar desse antecessor e passa a comparar esse número com seu “próximo anterior”, caso seja verdadeiro, o número da vez é inserido novamente no local desse número anterior e o mesmo é levado uma posição acima para abrir espaço para a nova inserção.

E assim essa tarefa é realizada em comparações com todos os seus vizinhos anteriores para colocá-lo em uma posição provisória até que todos tenham sido colocados em evidência para realmente definir onde é o local certo de cada número para que se concretize a ordenação.

Método CombSort:

O algoritmo Comb sort (ou Combo Sort ou ainda Algoritmo de pente) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz.

Um ganho significativo no método bubblesort pode ser obtido usando a estratégia de promover as chaves em direção às suas posições definitivas por saltos maiores do que apenas uma casa de cada vez.

Como funciona

- O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.

- Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre tem um gap (distância um do outro) de 1. A ideia básica do Comb sort é que a diferença pode ser muito mais do que um.