Como calcular a quantidade de comparações qsort

Boa tarde!

Índice Show

Definiç�o de Algoritmos
Descriç�o Narrativa
Linguagem Algoritma (Pseudoc�digo ou Portugol)
Algoritmos de Ordenaç�o
Bubble Sort
Selection Sort
Insertion sort
Estudo de caso
Conclus�o

Preciso de uma ajudinha de vocês. É o seguinte, o algoritmo abaixo para cada método que está comentado deveria me retornar o número de comparações que o algoritmo faz para ordenar os números em cada um dos métodos de ordenação.
Para o método de seleção (ordena) está ok. Já o inserção(insertionSort),o bolha(bubbleSort) e o quickSort não me é retornada a quantidade de comparações executadas para ordenação.

public class JavaApplication4 { static int i, j, tamanho; public static void ordena(int arranjo[]) { int i, j, menor, aux; int contador = 0; for (i = 0; i < tamanho - 1; i++) { menor = i; for (j = i + 1; j < tamanho; j++) { contador++; if (arranjo[j] < arranjo[menor]) { menor = j; } } aux = arranjo[menor]; arranjo[menor] = arranjo[i]; arranjo[i] = aux; } System.out.println("\n\ncontador = " + contador); } public static void insertionSort(int[] vetor) { int j; int key; int i = 0; int aux; int menor = 0; int contador = 0; for (j = 1; j < vetor.length; j++) { key = vetor[j]; for (i = j - 1; (i >= 0) && (vetor[i] > key); i--) { vetor[i + 1] = vetor[i]; } vetor[i + 1] = key; } aux = vetor[menor]; vetor[menor] = vetor[i]; vetor[i] = aux; System.out.println("\n\ncontador = " + contador); } public static void bubbleSort(int vetor[]) { boolean troca = true; int aux; int contador = 0; while (troca) { troca = false; for (int i = 0; i < vetor.length - 1; i++) { contador++; if (vetor[i] > vetor[i + 1]) { aux = vetor[i]; vetor[i] = vetor[i + 1]; vetor[i + 1] = aux; troca = true; } } System.out.println("\n\ncontador = " + contador); } } private static void quickSort(int[] vetor, int inicio, int fim) { if (inicio < fim) { int posicaoPivo = separar(vetor, inicio, fim); quickSort(vetor, inicio, posicaoPivo - 1); quickSort(vetor, posicaoPivo + 1, fim); } } private static int separar(int[] vetor, int inicio, int fim) { int pivo = vetor[inicio]; int i = inicio + 1, f = fim; while (i <= f) { if (vetor[i] <= pivo) i++; else if (pivo < vetor[f]) f--; else { int troca = vetor[i]; vetor[i] = vetor[f]; vetor[f] = troca; i++; f--; } } vetor[inicio] = vetor[f]; vetor[f] = pivo; return f; } public static void main (String[] args) { int vetor[]; tamanho = 10000; vetor = new int[tamanho]; Random gerador = new Random(); for (i = 0; i < tamanho; i++) { vetor[i] = i; } System.out.println(); for (i = 0; i < tamanho; i++) { System.out.print(" " + vetor[i]); } //CHAMA O METODO QUE SERÁ EXECUTADO quickSort(vetor); System.out.println(); for (i = 0; i < tamanho; i++) { System.out.print(" " + vetor[i]); } System.out.println("\n"); } private static void quickSort(int[] vetor) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } }

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.

Figura 1. Algor�timo �Calcular M�dia� em representaç�o de fluxograma.

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.

Figura 2. Esquema de funcionamento do Buble Sort.

� 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.

Figura 3. Esquema de funcionamento do Selection Sort.

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.

Figura 4. Esquema de funcionamento do Insertion Sort.

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.

Figura 5. Esquema de funcionamento do Quick Sort.

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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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

Algoritmo	Tempo(ms)	Comparaç�es	Movimentaç�es
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.