Entender o QuickSort..

[gRoOvE 0]

Bom, estou tentando entender como funciona esse método de ordenação, o problema surge quando começam as chamadas de recursvidade, debuguei usando o debug do visual C e ao mesmo tempo fui fazendo manualmente, escrevendo num papel msm. Certo momento o processamento chega ao final, ou seja, na última linha, e volta para a função recursiva (QuickSort(item,i,right);), não consigo entender oq acontece, se alguém puder dar uma luz ^^

 

void QuickSort(int *item,int left, int right)
{
	int i, j, pivo, troca;

	i = left;
	j = right;
	pivo = item[(left+right)/2];

	do
	{
		while(item[i]<pivo && i<right)
			i++;
		while(item[j]>pivo && j>left)
			j--;

		if(i<=j)
		{
			troca = item[i];
			item[i] = item[j];
			item[j] = troca;
			i++;
			j--;
		}
	}while(i<=j);
	if(left<j)
		QuickSort(item,left,j);
	if(right>i)
		QuickSort(item,i,right);
}

[Lukas 0]

Kara, dah uma conferida na famosa wikipedia "http://en.wikipedia.org/wiki/Quicksort", tem até uma figura mostrando a execução do quick lah!

[gRoOvE 0]

Já vi veio, acho que já li em uns 5 lugares diferentes a respeito...não consegui entender o que acontece no final, quando o compilador vai pra última linha de código e volta pras funções, nunca tinha visto isso "/

[quitZAUMMM 18]

como assim? você naum ta entendendo como ta funfando a recursividade nesse exemplo?

 

[]s

[José Enésio 4]

Acho que o que você quer dizer é isso aqui...

É que as chamadas das funções chamam outras funções, mas a função não acaba, quando a função mais atual termina, volta para a que chamou ela, que termina e volta para a que chamou ela, etc... até chegar ao fim de todas as funções.

[gRoOvE 0]

Acredito que a confusão seja essa msm Enésio...não sei como vou entender isso se nem debugando consigo visualizar realmente oq está acontecendo "/

[José Enésio 4]

O que está acontecendo é que as funções anteriores ainda não terminaram, elas apenas passaram para novas chamadas da função. Quando as funções mais recentes terminam, elas voltam para a anterior, e então terminam. Lembre-se que uma função não está terminada até atingir o return ou até chegar no final das chaves que demarcam o bloco de código.

É a mesma coisa se tivesse assim:

void meu()
{
   outra_funcao_qualquer();
   printf("bla bla bla");
}

A função outra_funcao_qualquer termina e retorna para meu, que então faz o printf e termina. Só que sem o printf, ela volta para a função e como não tem mais instruções, termina.

[gRoOvE 0]

Ahh isso sim, deforma genérica eu entendi, me referia a entender o processamento passo a passo :D