quick sort sem repetição de elementos

polska · March 17, 2013 at 11:10 PM

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 at 11:38 PM by polska

HappyHippyHippo · March 18, 2013 at 12:02 AM

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 at 12:03 AM by HappyHippyHippo

polska · March 18, 2013 at 12:09 AM

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 at 12:11 AM by polska

HappyHippyHippo · March 18, 2013 at 12:16 AM

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 · March 18, 2013 at 12:36 AM

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 at 12:39 AM by mogers

polska · March 18, 2013 at 01:33 AM

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 at 01:35 AM by polska

HappyHippyHippo · March 18, 2013 at 01:42 AM

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 · March 18, 2013 at 01:53 AM

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 at 01:53 AM by mogers

polska · March 18, 2013 at 02:00 AM

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 at 02:01 AM by polska

polska · March 18, 2013 at 01:06 PM

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 at 01:07 PM by polska

HappyHippyHippo · March 18, 2013 at 02:23 PM

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 · March 18, 2013 at 06:08 PM

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 · March 18, 2013 at 06:42 PM

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 · March 19, 2013 at 01:53 AM

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 · March 19, 2013 at 09:31 AM

sim

polska · March 20, 2013 at 03:40 PM

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 at 03:45 PM by polska

HappyHippyHippo · March 20, 2013 at 03:44 PM

vês como não era complicado 😉

Sign In

quick sort sem repetição de elementos

Recommended Posts

polska

HappyHippyHippo

polska

HappyHippyHippo

mogers

polska

HappyHippyHippo

mogers

polska

polska

HappyHippyHippo

polska

HappyHippyHippo

polska

HappyHippyHippo

polska

HappyHippyHippo

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information