Quicksort

dae galera,
alguem sabe o algoritimo do quicksort???
vlw

Opa… eu sei… Vc quer uma descrição de como ele funciona?

sim… poe uma breve descricao (q de pra entender hehehehe, jah vi em alguns sites e n entendi nada) e se possivel um ex pra ficar mais claro…
vlw

Vamos lá…

O quicksort é a classificação por troca de partição. Vc tem um vetor v com n elementos. Dai começa a lógica da ordenação: vc vai escolher sempre um elemento da partição que estiver desordenada (por exemplo o primeiro elemento). Depois de escolhido, este elemento do vetor será inserido na posição na qual, todos os elementos que o antecedem seja menor ou igual a ele e os que sucedem sejam maior que ele. Depois desse primeiro passo ai vc terá duas partições, onde vc aplicando está “fórmula” para as demais partições o vetor ficará ordenado.

Vamos para um exemplo (vai ficar mais claro).

[quote]
Vetor inicial: 25 57 48 37 12 92 86 33
Como foi descrito vou colocar o primeiro elemento do vetor na posição em que todos os elementos anteriores a ele sejam menores ou igual e os de sucedem sejam maiores.

Vetor: 12 (25) 57 48 37 92 86 33
Assim o 25 já está na sua posição correta, então pode “esquecer dele”.

Agora temos duas partições 12 e 57 48 37 92 86 33
É óbvio que se uma partição tem somente um elemento ele já esta ordenado, então a partição 12 já está ordenada.
Neste momento vc tem o seguinte vetor ordenado parcialmente:

                              12 25 57 48 37 92 86 33, onde o 12 e 25 já estão nas suas posições corretas.... pode "esquecer deles".

Agora temos a segunda partição: 57 48 37 92 86 33.
Como o 57 é o primeiro elemento desta partição, seguindo a formúla, vamos coloca-ló na posição que ele deve estar nesta partição. Fica assim:

                                     48 37 33 (57) 92 86

O 57 já está no seu lugar… então podemos “esquecer dele”. Assim o processo se repete para as demais partições, que neste momento ficaram duas outras vez: 48 37 33 e 92 86.

Até agora o vetor está assim: 12 25 48 37 33 57 92 86, ou seja, o 12, 25 e o 57 já estão em suas posições corretas… e o processo continua até todo o vetor ficar ordenado.

Blz… tentei ser bem claro e objetivo e didático… espero ter ajudado…[/quote]

:idea:
Ta aí o código:

[code]public void quickSort( int conjunto[], int inicio, int fim )
{
int pivo, trab, i, j;
i = inicio;
j = fim;
pivo = conjunto[ ( i + j ) / 2 ];

do
{
	while ( conjunto[ i ] < pivo ) 
		i++;
	
	while ( conjunto[ j ] > pivo ) 
		j--;
	
	if ( i <= j ) 
	{
		trab = conjunto[ i ];
		conjunto[ i ] = conjunto[ j ];
		conjunto[ j ] = trab;
		i = i + 1;
		j = j ? 1;
	}
	
} while ( i <= j );

if ( inicio < j ) 
	quickSort( conjunto, inicio, j );
if ( fim > i ) 
	quickSort ( conjunto, i, fim );

}[/code]

Vê se e isso que vc precisa?
[color=“red”]
editado para conter BBCode code por JuJo[/color]