Ir para o conteúdo
polska

quick sort sem repetição de elementos

Mensagens Recomendadas

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);
}

Editado por polska

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por HappyHippyHippo
  • Voto 1

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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..

Editado por polska

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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 :)

Editado por polska

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por polska

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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);
}

Editado por polska

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por polska

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

Partilhar esta mensagem


Ligação 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

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.