Problemas s�o quest�es propostas em busca de uma soluç�o. Com o prop�sito de conceder uma soluç�o para certo problema, existem os algoritmos, cada problema que � decid�vel possui um algoritmo que determina uma soluç�o para cada inst�ncia desse problema.
Algoritmos descrevem passo a passo os procedimentos para chegar a uma soluç�o de um problema e podem ser representados de tr�s formas:
- A forma de descriç�o narrativa, na qual se usa a linguagem nativa de quem escreve. Essa forma n�o segue um padr�o definido e pode sofrer v�rias interpretaç�es por quem l�;
- Outra forma de representar um algoritmo � o fluxograma, uma representaç�o visual que utiliza s�mbolos que s�o figuras geom�tricas, cada uma com sua funç�o espec�fica. Essa representaç�o, como o pr�prio nome diz, mostra o fluxo do algoritmo e tamb�m elimina as v�rias interpretaç�es que a descriç�o narrativa permitia sobre um algoritmo;
- Por �ltimo, existe a linguagem algoritma [Pseudoc�digo ou Portugol] que � a que mais se aproxima da estrutura de uma linguagem estruturada.
Um tipo de algoritmo muito usado na resoluç�o de problemas computacionais s�o os algoritmos de ordenaç�o, que servem para ordenar/organizar uma lista de n�meros ou palavras de acordo com a sua necessidade. As linguagens de programaç�o j� possuem m�todos de ordenaç�o, mas � bom saber como funcionam os algoritmos, pois h� casos de problemas em que o algoritmo de ordenaç�o gen�rico n�o resolve, �s vezes � necess�rio modific�-lo.
Os mais populares algoritmos de ordenaç�o s�o: Insertion sort, Selection sort, Bubble sort, Comb sort, Quick sort, Merge sort, Heap sort e Shell sort. Neste artigo ser�o estudados os algoritmos Bubble sort, Selection Sort, Quick sort e o Insertion sort, explicando o funcionamento de cada um deles.
Definiç�o de Algoritmos
O Algoritmo � um esquema de resoluç�o de um problema. Pode ser implementado com qualquer sequ�ncia de valores ou objetos que tenham uma l�gica infinita [por exemplo, a l�ngua portuguesa, a linguagem Pascal, a linguagem C, uma sequ�ncia num�rica, um conjunto de objetos tais como l�pis e borracha], ou seja, qualquer coisa que possa fornecer uma sequ�ncia l�gica.
Podemos ilustrar um algoritmo pelo exemplo de uma receita culin�ria, embora muitos algoritmos sejam mais complexos. Um Algoritmo mostra passo a passo os procedimentos necess�rios para resoluç�o de um problema.
Descriç�o Narrativa
A descriç�o narrativa � o uso da sua l�ngua nativa para descriç�o dos passos para se resolver um problema.
A vantagem dessa forma de representaç�o � que qualquer um pode faz�-la sem ter conhecimentos avançados.
A desvantagem � que n�o h� um padr�o, cada pessoa pode escrever como quiser. Outra desvantagem � a imprecis�o, ou seja, a descriç�o pode n�o ficar clara e pode-se tirar v�rias interpretaç�es diferentes de um mesmo algoritmo.
Abaixo temos um exemplo de algoritmo usando a descriç�o narrativa:
In�cio Passo 1: Obter os valores de n1,n2,n3; Passo 2: Somar os valores do passo 1; Passo 3: Dividir o resultado obtido no Passo 2 por 3; Passo 4: Se o resultado do Passo 3 for maior ou igual a 6 ent�o escreva �Parab�ns voc� foi aprovado�, sen�o, escreva �Infelizmente voc� ficou de exame� e v� para o fim do programa Fim
Listagem 1. Algoritmo �Calculando a m�dia� em descriç�o narrativa.
Fluxograma
O fluxograma passou a ser usado para eliminar ambiguidades dos algoritmos. S�o s�mbolos gr�ficos padronizados, cada um representado por uma forma geom�trica que implica em uma aç�o, instruç�o ou um comando distinto.
Esta forma � intermedi�ria a descriç�o narrativa e ao pseudoc�digo, pois � mais precisa do que a primeira, por�m, n�o se preocupa com detalhes de implementaç�o do programa, como os tipos das vari�veis usadas.
Linguagem Algoritma [Pseudoc�digo ou Portugol]
Essa forma de representaç�o surgiu para tentar suprir as defici�ncias das outras representaç�es. Consiste na definiç�o de uma pseudolinguagem de programaç�o, cujos comandos s�o em portugu�s, mas que j� lembram um pouco a estrutura de uma linguagem de programaç�o estruturada, ou seja, a pseudolinguagem se assemelha muito ao modo como os programas s�o escritos. Isso vai permitir que os algoritmos sejam traduzidos, quase que diretamente, para uma linguagem de programaç�o.
algoritmo �CalcularMedia� var n1,n2,n3,media :real; inicio leia[n1,n2,n3]; media← [n1+n2+n3]/3; se media>=6 entao escreva[�Parab�ns voc� foi aprovado�]; sen�o escreva[�Infelizmente voc� ficou de exame�]; Fimse fimalgoritmo
Listagem 2. Algoritmo �Calcular M�dia� em linguagem algoritma.
Algoritmos 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. O objetivo da ordenaç�o � facilitar a recuperaç�o dos dados de uma lista.
Para este artigo foram escolhidos alguns algoritmos de ordenaç�o para serem estudados que s�o: Bubble Sort, Selection Sort, Quick Sort e Insertion Sort.
Bubble Sort
Bubble sort � o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posiç�o i ser� comparado com o elemento da posiç�o i + 1, ou seja, um elemento da posiç�o 2 ser� comparado com o elemento da posiç�o 3. Caso o elemento da posiç�o 2 for maior que o da posiç�o 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execuç�o, o vetor ter� que ser percorrido quantas vezes que for necess�ria, tornando o algoritmo ineficiente para listas muito grandes.
- � verificado se o 3 � maior que 5, por essa condiç�o ser falsa, n�o h� troca.
- � verificado se o 5 � maior que 1, por essa condiç�o ser verdadeira, h� uma troca.
- � verificado se o 5 � maior que 2, por essa condiç�o ser verdadeira, h� uma troca.
- � verificado se o 5 � maior que 4, por essa condiç�o ser verdadeira, h� uma troca.
- O m�todo retorna ao in�cio do vetor realizando os mesmos processos de comparaç�es, isso � feito at� que o vetor esteja ordenado.
Selection Sort
Este algoritmo � baseado em se passar sempre o menor valor do vetor para a primeira posiç�o [ou o maior dependendo da ordem requerida], depois o segundo menor valor para a segunda posiç�o e assim sucessivamente, at� os �ltimos dois elementos.
Neste algoritmo de ordenaç�o � escolhido um n�mero a partir do primeiro, este n�mero escolhido � comparado com os n�meros a partir da sua direita, quando encontrado um n�mero menor, o n�mero escolhido ocupa a posiç�o do menor n�mero encontrado. Este n�mero encontrado ser� o pr�ximo n�mero escolhido, caso n�o for encontrado nenhum n�mero menor que este escolhido, ele � colocado na posiç�o do primeiro n�mero escolhido, e o pr�ximo n�mero � sua direita vai ser o escolhido para fazer as comparaç�es. � repetido esse processo at� que a lista esteja ordenada.
- Neste passo o primeiro n�mero escolhido foi o 3, ele foi comparado com todos os n�meros � sua direita e o menor n�mero encontrado foi o 1, ent�o os dois trocam de lugar.
- O mesmo processo do passo 1 acontece, o n�mero escolhido foi o 5 e o menor n�mero encontrado foi o 2.
- N�o foi encontrado nenhum n�mero menor que 3, ent�o ele fica na mesma posiç�o.
- O n�mero 5 foi escolhido novamente e o �nico n�mero menor que ele � sua direita � o 4, ent�o eles trocam.
- Vetor j� ordenado.
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.
- Neste passo � verificado se o 5 � menor que o 3, como essa condiç�o � falsa, ent�o n�o h� troca.
- � verificado se o quatro � menor que o 5 e o 3, ele s� � menor que o 5, ent�o os dois trocam de posiç�o.
- � verificado se o 2 � menor que o 5, 4 e o 3, como ele � menor que 3, ent�o o 5 passa a ocupar a posiç�o do 2, o 4 ocupa a posiç�o do 5 e o 3 ocupa a posiç�o do 4, assim a posiç�o do 3 fica vazia e o 2 passa para essa posiç�o.
O mesmo processo de comparaç�o acontece com o n�mero 1, ap�s esse processo o vetor fica ordenado.
Quick sort
O Quicksort � o algoritmo mais eficiente na ordenaç�o por comparaç�o. Nele se escolhe um elemento chamado de piv�, a partir disto � organizada a lista para que todos os n�meros anteriores a ele sejam menores que ele, e todos os n�meros posteriores a ele sejam maiores que ele. Ao final desse processo o n�mero piv� j� est� em sua posiç�o final. Os dois grupos desordenados recursivamente sofreram o mesmo processo at� que a lista esteja ordenada.
- O n�mero 3 foi escolhido como piv�, nesse passo � procurado � sua direita um n�mero menor que ele para ser passado para a sua esquerda. O primeiro n�mero menor encontrado foi o 1, ent�o eles trocam de lugar.
- Agora � procurado um n�mero � sua esquerda que seja maior que ele, o primeiro n�mero maior encontrado foi o 5, portanto eles trocam de lugar.
- O mesmo processo do passo 1 acontece, o n�mero 2 foi o menor n�mero encontrado, eles trocam de lugar.
- O mesmo processo do passo 2 acontece, o n�mero 4 � o maior n�mero encontrado, eles trocam de lugar.
- O vetor desse exemplo � um vetor pequeno, portanto ele j� foi ordenado, mas se fosse um vetor grande, ele seria dividido e recursivamente aconteceria o mesmo processo de escolha de um piv� e comparaç�es.
Estudo de caso
Para realizaç�o pr�tica deste artigo, foram feito testes com os algoritmos estudados, os testes foram os seguintes:
Verificar o comportamento dos algoritmos em relaç�o ao tempo, movimentaç�es de trocas e comparaç�es.
Foram testadas 3 ordens de listas com 3 tamanhos diferentes cada:
- Ordem 1: lista ordenada em ordem crescente.
- Ordem 2: lista ordenada em ordem decrescente.
- Ordem 3: lista desordenada com n�meros aleat�rios.
Os resultados foram o seguintes:
Ordem 1
Tamanho do vetor: 100
Bubble sort | 0,0988 | 5050 | 0 |
Selection Sort | 0,0602 | 4950 | 297 |
Insertion sort | 0,0038 | 99 | 198 |
Quick sort | 0,0141 | 606 | 189 |
Tamanho do vetor: 1000
Bubble sort | 9,5415 | 500500 | 0 |
Selection Sort | 5,4587 | 499500 | 2997 |
Insertion sort | 0,0359 | 999 | 1998 |
Quick sort | 0,1602 | 9009 | 1533 |
Tamanho do vetor: 10000
Bubble sort | 934,5364 | 50005000 | 0 |
Selection Sort | 508,5891 | 49995000 | 29997 |
Insertion sort | 0,3558 | 9999 | 19998 |
Quick sort | 2,0824 | 125439 | 17712 |
Ordem 2
Tamanho do vetor: 100
Bubble sort | 0,2045 | 5050 | 14850 |
Selection Sort | 0,0750 | 4950 | 297 |
Insertion sort | 0,1173 | 99 | 5148 |
Quick sort | 0,0147 | 610 | 336 |
Tamanho do vetor: 1000
Bubble sort | 20,3377 | 500500 | 1498500 |
Selection Sort | 6,9038 | 499500 | 2997 |
Insertion sort | 11,4277 | 999 | 501498 |
Quick sort | 0,1622 | 9016 | 3030 |
Tamanho do vetor: 10000
Bubble sort | 1838,0272 | 50005000 | 149985000 |
Selection Sort | 665,2050 | 49995000 | 29997 |
Insertion sort | 1074,1171 | 9999 | 50014998 |
Quick sort | 2,1279 | 125452 | 32712 |
Ordem 3
Tamanho do vetor: 100
Bubble sort | 0,1596 | 5050 | 6777 |
Selection Sort | 0,0698 | 4950 | 297 |
Insertion sort | 0,0570 | 99 | 2457 |
Quick sort | 0,0314 | 897 | 576 |
Tamanho do vetor: 1000
Bubble sort | 16,6730 | 500500 | 756840 |
Selection Sort | 5,6664 | 499500 | 2997 |
Insertion sort | 5,7523 | 999 | 254278 |
Quick sort | 0,3725 | 13138 | 7983 |
Tamanho do vetor: 10000
Bubble sort | 1455,9734 | 50005000 | 74237889 |
Selection Sort | 545,1068 | 49995000 | 29997 |
Insertion sort | 539,6891 | 9999 | 24765961 |
Quick sort | 4,5072 | 176065 | 103635 |
Conclus�o
Com base nos testes realizados foram obtidas as seguintes conclus�es:
Bubble sort
Para listas j� ordenadas em ordem crescente � o �nico algoritmo que n�o realiza movimentaç�es, mas em compensaç�o � o que tem o maior tempo e o maior n�mero de comparaç�es. N�o s� em listas j� ordenadas, mas em todos os casos o bubble sort se mostrou um algoritmo ineficiente.
Selection sort
Nas listas de ordem 1 e ordem 3, o selection sort foi o segundo pior algoritmo, mas se mostrou mais eficiente do que o Insertion sort em relaç�o ao tempo e a quantidade de movimentaç�es na lista de ordem 2.
Insertion Sort
Na lista de ordem 1, o Insertion sort se mostrou mais eficiente que todos os outros algoritmos em relaç�o ao tempo e comparaç�es. Na lista de ordem 2 foi menos eficiente do que o selection sort e na lista de ordem 3 a diferença de tempo entre o insertion e o selection foi pequena.
Quick Sort
O quick sort certamente � o algoritmo mais eficiente em listas totalmente desordenadas, ele se torna muito eficiente em relaç�o aos outros no quesito de tempo. Na lista de ordem 3 e na de ordem 2 a diferença de tempo do quick sort em comparaç�o aos outros foi absurdamente grande.
Refer�ncias bibliogr�ficas- Bubble sort
- Quicksort
- Insertion sort