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

Sign in to follow this  
polska

quick sort sem repetição de elementos

Recommended Posts

polska

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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 by HappyHippyHippo
  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
polska

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 :D , 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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
mogers

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 by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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.


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
mogers

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 by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
polska

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
polska

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
polska

Não estou a entender.. :confused:

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 ...


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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.


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
polska

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?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
polska

finally :D

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 :D

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.