quick sort sem repetição de elementos

[polska 12]

Boas pessoal, estava a fazer um programita e precisava de ordenar arrays que podem chegar aos 50 000 elementos, e decidi usar o quick sort. Até aqui tudo bem, mas ao mesmo tempo preciso de manter os números de ordem de cada um dos elementos, e é aqui que surge o problema. Eu fiz a função e quando fosse para fazer alguma troca, fazia nos dois arrays, o de alturas, e o de numeros_ordem, e também coloquei uma condição que não deixa trocar posições onde o elemento seja igual.. O que se sucede é que está tudo a ser ordenado muito bem, quando aparece o primeiro par de números iguais ele não troca de posições, mas a partir daí quando voltam a aparecer pares de números iguais, ele já troca as posições, eu não estou a perceber porquê..

exemplo:

o array inicial: 350 150 200 400 831 450 200 350 100 350

o array ordenado: 100 150 200 200 350 350 350 400 450 831

o array de números de ordem: 9 2 3 7 8 1 10 4 6 5

Como podem ver no caso do 200 os números de ordem estão ordenados correctamente, já para o 350 não.. Alguma ajuda?

void quick_sort(int esq, int dir)
{
       int i = esq, j = dir, tmp;
       int pivot = alturas[(i+j)/2];

       /* divisória */
       while(i<=j)
       {
               while(alturas[i]<pivot)
                       i++;
               while(alturas[j]>pivot)
                       j--;

               if(i<=j)
               {
                   if(alturas[i] != alturas[j])
                   {
                       tmp = alturas[j];
                       alturas[j] = alturas[i];
                       alturas[i] = tmp;

                       tmp = numeros_ordem[j];
                       numeros_ordem[j] = numeros_ordem[i];
                       numeros_ordem[i] = tmp;
                   }

                   i++; j--;
               }
       };

       /* recursividade */
       if(j > esq)
               quick_sort(esq, j);
       if(i < dir)
               quick_sort(i, dir);
}

Edited March 17, 2013 by polska

[HappyHippyHippo 1,162]

primeiro de tudo, o teu código cheira a variáveis globais ...

e que tal, em vez dessa complicação toda criasses um array auxiliar desta maneira:

#include <stdio.h>
#include <string.h>

int compare_long(const void * a, const void * b)
{
 // calcular a diferença entre valores
 int result = (*(long*)a >> 32) - (*(long*)b >> 32);

 // verificar se a diferença é igual, se sim, comparar indices
 if (result == 0)
 {
   result = (*(long*)a & 0xffffffff) - (*(long*)b & 0xffffffff);
 }

 return result;
}

int main()
{
 int array_a_ordenar[] = {350, 150, 200, 400, 831, 450, 200, 350, 100, 350};
 size_t array_size = sizeof (array_a_ordenar) / sizeof (int);
 long array_auxiliar[array_size];
 int i;

 // criação do array auxiliar
 for (i = 0; i < array_size; i++)
 {
   // nota que adicionei +1 para ser igual aos teus indices
   array_auxiliar[i] = ((long)array_a_ordenar[i] << 32) + (i + 1);
 }

 // oredenação simples com quick-sort do array_auxiliar (nada de maroscas)

 // exemplo do resutlado com qsort
 qsort(array_auxiliar, array_size, sizeof (long), compare_long);

 // como ler os valores ordenados
 for(i = 0; i < array_size; i++)
 {
   printf("elemento %ld | indice %ld\n", array_auxiliar[i] >> 32, array_auxiliar[i] & 0xffffffff);
 }

 return 0;
}

output

elemento 100 | indice 9
elemento 150 | indice 2
elemento 200 | indice 3
elemento 200 | indice 7
elemento 350 | indice 1
elemento 350 | indice 8
elemento 350 | indice 10
elemento 400 | indice 4
elemento 450 | indice 6
elemento 831 | indice 5

Edited March 18, 2013 by HappyHippyHippo

[polska 12]

primeiro de tudo, o teu código cheira a variáveis globais ...

e que tal, em vez dessa complicação toda criasses um array auxiliar desta maneira:

#include <stdio.h>
#include <string.h>

int compare_long(const void * a, const void * b)
{
 // calcular a diferença entre valores
 int result = (*(long*)a >> 32) - (*(long*)b >> 32);

 // verificar se a diferença é igual, se sim, comparar indices
 if (result == 0)
 {
   result = (*(long*)a & 0xffffffff) - (*(long*)b & 0xffffffff);
 }

 return result;
}

int main()
{
 int array_a_ordenar[] = {350, 150, 200, 400, 831, 450, 200, 350, 100, 350};
 size_t array_size = sizeof (array_a_ordenar) / sizeof (int);
 long array_auxiliar[array_size];
 int i;

 // criação do array auxiliar
 for (i = 0; i < array_size; i++)
 {
   // nota que adicionei +1 para ser igual aos teus indices
   array_auxiliar[i] = ((long)array_a_ordenar[i] << 32) + (i + 1);
 }

 // oredenação simples com quick-sort do array_auxiliar (nada de maroscas)

 // exemplo do resutlado com qsort
 qsort(array_auxiliar, array_size, sizeof (long), compare_long);

 // como ler os valores ordenados
 for(i = 0; i < array_size; i++)
 {
   printf("elemento %ld | indice %ld\n", array_auxiliar[i] >> 32, array_auxiliar[i] & 0xffffffff);
 }

 return 0;
}

output

elemento 100 | indice 9
elemento 150 | indice 2
elemento 200 | indice 3
elemento 200 | indice 7
elemento 350 | indice 1
elemento 350 | indice 8
elemento 350 | indice 10
elemento 400 | indice 4
elemento 450 | indice 6
elemento 831 | indice 5

@Happy, cheirou-te bem então , não é costume eu fazer isto.

Eu antes de implementar "à mão" o quick sort, também tinha já feito com o qsort, o problema é que eu tenho que fazer dois swaps em vez de apenas um, porque estou a ordenar dois arrays e um deles é o numeros de ordem que são ordenado dependendo do arraay das alturas... E já vi que o teu código faz isso mas eu não percebi para ser sincero... Não podes explicar o que está mal ou que tenho de alterar no meu código? É que mesmo a função compare do qsort que fizeste me trocou todo, visto que não entendo muito bem bitwises..

Edited March 18, 2013 by polska

[HappyHippyHippo 1,162]

ok, não vou explicar os bitwise ...

o teu problema está aqui:

               while(alturas[i]<pivot)
                       i++;
               while(alturas[j]>pivot)
                       j--;

a questão é, não basta comparar o valor dos elementos, porque isso não te diz nada sobre a ordem original destes.

o que tens de implementar é que na verificação, se os elementos forem iguais, os índices também necessitam de seguir a ordem

[mogers 13]

Se escolheres um pivot numa posição fixa, é fácil apanhares um input que faça o teu quick sort correr em O(N^2). Um mecanismo um pouco melhor e simples é usar um elemento aleatorio entre "esq" e "dir".

Tive a fazer a disciplina de Algorithm Design and Analysis no Coursera e lá explicam uma implementação que gostei mais:

void partition(int * v, int a, int b) {
 if (a >= b)
return;
 int i , j , pivot = a + rand() % (b-a+1);
 swap( v[a], v[pivot] );
 i = a+1;
 for (j = a+1; j <= b; j++)
if (v[j] < v[a]) {  // o pivot fica na posição 'a', aqui terias de ter em conta as alturas e os numeros de ordem
  swap( v[i], v[j] );
  i++;
}
 swap( v[a], v[i-1] );
 partition( a, i-2 );
 partition( i, b );
}

A explicação da implementação está nos videos das aulas.

Edited March 18, 2013 by mogers

[polska 12]

ok, não vou explicar os bitwise ...

o teu problema está aqui:

               while(alturas[i]<pivot)
                       i++;
               while(alturas[j]>pivot)
                       j--;

a questão é, não basta comparar o valor dos elementos, porque isso não te diz nada sobre a ordem original destes.

o que tens de implementar é que na verificação, se os elementos forem iguais, os índices também necessitam de seguir a ordem

Deixa-me ver se entendi.. Eu continuo a necessitar de fazer essas comparações para aumentar o i e j, mas tenho que verificar também (sempre que aumento uma vez o i e j) se os elementos são iguais, e troco se o número de ordem de i for maior que o de j.. Estou a pensar num único while para fazer isto.. Está correcto?

Se escolheres um pivot numa posição fixa, é fácil apanhares um input que faça o teu quick sort correr em O(N^2). Um mecanismo um pouco melhor e simples é usar um elemento aleatorio entre "esq" e "dir".

Tive a fazer a disciplina de Algorithm Design and Analysis no Coursera e lá explicam uma implementação que gostei mais:

void partition(int * v, int a, int b) {
 if (a >= b)
   return;
 int i , j , pivot = a + rand() % (b-a+1);
 swap( v[a], v[pivot] );
 i = a+1;
 for (j = a+1; j <= b; j++)
   if (v[j] < v[a]) {  // o pivot fica na posição 'a', aqui terias de ter em conta as alturas e os numeros de ordem
     swap( v[i], v[j] );
     i++;
   }
 swap( v[a], v[i-1] );
 partition( a, i-2 );
 partition( i, b );
}

A explicação da implementação está nos videos das aulas.

Eu já tinha lido que o quick sort pode em alguns casos correr em O(N^2), mas não sabia como prevenir ou diminuir as possibilidades de isto acontecer, obrigado

Edited March 18, 2013 by polska

[HappyHippyHippo 1,162]

Se escolheres um pivot numa posição fixa, é fácil apanhares um input que faça o teu quick sort correr em O(N^2). Um mecanismo um pouco melhor e simples é usar um elemento aleatorio entre "esq" e "dir".

cuidado : é certo que é mais fácil acontecer o dizes (simplesmente pela particularidade da escolha) no entanto a probabilidade de ocorrência do conjunto a ordenar que leva a O(N²) tanto num como no outro algoritmo é o mesmo.

[mogers 13]

Deixa-me ver se entendi.. Eu continuo a necessitar de fazer essas comparações para aumentar o i e j, mas tenho que verificar também (sempre que aumento uma vez o i e j) se os elementos são iguais, e troco se o número de ordem de i for maior que o de j.. Estou a pensar num único while para fazer isto.. Está correcto?

Simplificando, apenas tens de redefinir o teu conceito de uma coisa ser menor do que a outra. Se tens inteiros, apenas usas o <, como tens um par, se a altura for igual só é menor se o seu numero de ordem for menor do que o outro.

Eu já tinha lido que o quick sort pode em alguns casos correr em O(N^2), mas não sabia como prevenir ou diminuir as possibilidades de isto acontecer, obrigado

Prevenir é impossivel porque o worst case é O(N^2). Tens a explicação nas tais aulas. Há outras estrategias como escolher 3 numeros aleatorios do range esq-dir e escolher a mediana como pivot.

cuidado : é certo que é mais fácil acontecer o dizes (simplesmente pela particularidade da escolha) no entanto a probabilidade de ocorrência do conjunto a ordenar que leva a O(N²) tanto num como no outro algoritmo é o mesmo.

Sim, claro, nem eu disse o contrário.

Eu falei assim porque penso que ele está a tentar resolver um exercício de concursos de programação (o exemplo das alturas não me é estranho) e escolher o elemento médio é tão clássico que o juri podia ser mauzinho e facilmente colocar um caso de teste para minar esta abordagem.

Edited March 18, 2013 by mogers

[polska 12]

Simplificando, apenas tens de redefinir o teu conceito de uma coisa ser menor do que a outra. Se tens inteiros, apenas usas o <, como tens um par, se a altura for igual só é menor se o seu numero de ordem for menor do que o outro.

Entendido, obrigado .

Sim, claro, nem eu disse o contrário.

Eu falei assim porque penso que ele está a tentar resolver um exercício de concursos de programação (o exemplo das alturas não me é estranho) e escolher o elemento médio é tão clássico que o juri podia ser mauzinho e facilmente colocar um caso de teste para minar esta abordagem.

Sim, qualificação 2007 - ONI

Edited March 18, 2013 by polska

[polska 12]

Não é suposto funcionar desta maneira?

void quick_sort(int esq, int dir)
{
       int i = esq, j = dir, tmp;
       int pivot = alturas[(i+j)/2];

       /* divisória */
       while(i<=j)
       {

               while(alturas[i]<pivot)
                       i++;
               while(alturas[j]>pivot)
                       j--;		

			if(alturas[i] == alturas[j] && i<=j)
			{
				if(numeros_ordem[i] > numeros_ordem[j])
				{
						tmp = numeros_ordem[j];
						numeros_ordem[j] = numeros_ordem[i];
						numeros_ordem[i] = tmp;

						i++; j--;
				}
			}
			else if(i<=j)
			{
				tmp = alturas[j];
				alturas[j] = alturas[i];
				alturas[i] = tmp;

				tmp = numeros_ordem[j];
				numeros_ordem[j] = numeros_ordem[i];
				numeros_ordem[i] = tmp;

				i++; j--;
			}
       };

       /* recursividade */
       if(j > esq)
               quick_sort(esq, j);
       if(i < dir)
               quick_sort(i, dir);
}

Edited March 18, 2013 by polska

[HappyHippyHippo 1,162]

ok, não vou explicar os bitwise ...

o teu problema está aqui:

               while(alturas[i]<pivot)
                       i++;
               while(alturas[j]>pivot)
                       j--;

a questão é, não basta comparar o valor dos elementos, porque isso não te diz nada sobre a ordem original destes.

o que tens de implementar é que na verificação, se os elementos forem iguais, os índices também necessitam de seguir a ordem

[polska 12]

Não estou a entender..

Eu vou precisar de encontrar os mesmo valores < ou > que o pivot, então deixo na mesma esses whiles, e depois quando encontrar verifico se os elementos são iguais, ai só troco os indices se o de i for < que o de j ...

[HappyHippyHippo 1,162]

o que estás a fazer com os ciclos while é considerar os elementos menores ou maiores que o pivot. o que tens de fazer é além de considerar o valor, tens de considerar o índice se o valor é igual ao pivot.

[polska 12]

o que estás a fazer com os ciclos while é considerar os elementos menores ou maiores que o pivot. o que tens de fazer é além de considerar o valor, tens de considerar o índice se o valor é igual ao pivot.

quando te referes a considerar o índice, é os números de ordem correcto?

[HappyHippyHippo 1,162]

sim

[polska 12]

finally

while(alturas[i]<pivot || (alturas[i]==pivot && numeros_ordem[i]<pivot_indice))
					i++;
			while(alturas[j]>pivot || (alturas[j]==pivot && numeros_ordem[j]>pivot_indice))
					j--;

Obrigado

ps: apesar deste trabalho todo, agora que vejo, para o output do problema, é preferível ter os índices ordenados ao contrário... enfim, valeu pelo que aprendi

Edited March 20, 2013 by polska

[HappyHippyHippo 1,162]

vês como não era complicado