QuickSort e a Partição

[willyboy]

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 😉

[Rui Carlos]

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

[willyboy]

Usei...

44 55 12 52 46 (pivot) 94 6 18 67

[Rui Carlos]

Com esse valores, a função está a funcionar.

[mogers]

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

[Rui Carlos]

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

[willyboy]

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 😛

[Jeronimus Linuxius]

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 😛

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

[Rui Carlos]

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 😛 ) é trivial de se implementar...

[Jeronimus Linuxius]

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 😄 ) é trivial de se implementar...

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

JJ

[Rui Carlos]

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.

[Jeronimus Linuxius]

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