• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

willyboy

QuickSort e a Partição

12 mensagens neste tópico

Boa noite,

Estou a tentar construir o algoritmo de partição utilizado no QuickSort... Aqui está o código com o qual estou a tentar...

int particao (int v[], int a, int b)
{
int esq = a, dir = b, pvt = v[(a + b)/2];

printf("[Pivot: %d] ", pvt);

do
{
	while (v[esq] < pvt)
		esq++;

	while (v[dir] > pvt)
		dir--;

	if (esq <= dir)
	{
		troca(v, esq, dir);
		esq++;
		dir--;
	}
}
while (esq <= dir);

return dir;						/* índice do elemento já colocado na posição correcta */
}

Este código trabalha bem para vectores com pequenas dimensões (à volta de 6 elementos)... No entanto fiz um teste com 9 e deixou.me elementos fora do sítio... Não consigo perceber o que está errado... Agluém conhece um algoritmo eficiente de partição?

Muito obrigado ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Assim à primeira vista, não estou a ver o erro. Que valores é que usaste?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O quicksort não funciona só com essa função "partição"... só estás a usar essa ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pelo que ele disse, aquilo é apenas o algoritmo (função) de partição usado no QS.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens razão, agora está a funcionar com esses números, mas há certos vectores para os quais não funciona :S

Eu só estou mesmo interessado na função de partição :) não é para o quicksort em si, mas para aplicar noutra coisa :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens razão, agora está a funcionar com esses números, mas há certos vectores para os quais não funciona :S

Eu só estou mesmo interessado na função de partição :P não é para o quicksort em si, mas para aplicar noutra coisa :P

O Quicksort é bastante complicadinho de implementar... No entanto, estou a ver um leve erro em que provavelmente caiste...

O problema de partir o vector em dois não pode ser isolado dessa forma. Repara bem: o passo do Quicksort é "Divide-se o vector em dois. O de baixo só tem elementos menores ou iguais ao pivot, enquanto que o de cima só tem elementos maiores ou iguais ao pivot." (pela propriedade transitiva, qualquer elemento do vector de baixo é menor ou igual a qualquer dos elementos do vector superior).

Não diz em lado nenhum que o "ponto de partição", assim o chamemos, fica situado ao lado da posição original do pivot, nem que fica situado a meio do vector. Rigorosamente falando, até se pode observar que o pivot não precisa sequer de estar no vector.

O ponto de partição é, a menos que eu esteja a ver mal, à direita do elemento onde pára o índice j (mesmo que o índice "i" vá parar muito mais abaixo).

PS: Não testei... É só mesmo um palpite (btw, implementei ainda ontem um quicksort em scheme e garanto que não é fácil... mas eu não implementei bem assim...).

PS2: Se ainda andares por aqui e ainda não tiveres resolvido o problema, diz qualquer coisa!

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O Quicksort é bastante complicadinho de implementar... No entanto, estou a ver um leve erro em que provavelmente caiste...

O problema de partir o vector em dois não pode ser isolado dessa forma. Repara bem: o passo do Quicksort é "Divide-se o vector em dois. O de baixo só tem elementos menores ou iguais ao pivot, enquanto que o de cima só tem elementos maiores ou iguais ao pivot." (pela propriedade transitiva, qualquer elemento do vector de baixo é menor ou igual a qualquer dos elementos do vector superior).

Não diz em lado nenhum que o "ponto de partição", assim o chamemos, fica situado ao lado da posição original do pivot, nem que fica situado a meio do vector. Rigorosamente falando, até se pode observar que o pivot não precisa sequer de estar no vector.

O ponto de partição é, a menos que eu esteja a ver mal, à direita do elemento onde pára o índice j (mesmo que o índice "i" vá parar muito mais abaixo).

PS: Não testei... É só mesmo um palpite (btw, implementei ainda ontem um quicksort em scheme e garanto que não é fácil... mas eu não implementei bem assim...).

PS2: Se ainda andares por aqui e ainda não tiveres resolvido o problema, diz qualquer coisa!

Não percebi nada do teu post :/

Afinal onde é que está o erro? É que eu continuo a achar que aquilo funciona (embora possa não ser a melhor partição para o Quick Sort).

PS: A implementação é complicada em C (e, talvez, na maioria das linguagens), mas noutras linguagens (como Haskell :P) é trivial de se implementar...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi nada do teu post :/

Afinal onde é que está o erro? É que eu continuo a achar que aquilo funciona (embora possa não ser a melhor partição para o Quick Sort).

Quiz dizer que o ponto onde os dois novos vectores se separam não tem necessariamente de ser o ponto de onde o pivot foi inicialmente "pescado"...

De qualquer das formas, não sei se ele assumiu isso ou não.

PS: A implementação é complicada em C (e, talvez, na maioria das linguagens), mas noutras linguagens (como Haskell :D) é trivial de se implementar...

A programação funcional faz maravilhas... Pena é eu não a conhecer bem!...

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quiz dizer que o ponto onde os dois novos vectores se separam não tem necessariamente de ser o ponto de onde o pivot foi inicialmente "pescado"...

De qualquer das formas, não sei se ele assumiu isso ou não.

Penso que isso não está a acontecer.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Penso que isso não está a acontecer.

É possível. Foi só um palpite (baseado no facto de a função do post original não comunicar à função que a chamou o ponto onde o vector ficou dividido)...

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora