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]