polska Posted March 17, 2013 at 11:10 PM Report #499510 Posted March 17, 2013 at 11:10 PM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 18, 2013 at 12:02 AM Report #499513 Posted March 18, 2013 at 12:02 AM (edited) 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 1 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted March 18, 2013 at 12:09 AM Author Report #499514 Posted March 18, 2013 at 12:09 AM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 18, 2013 at 12:16 AM Report #499515 Posted 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 IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
mogers Posted March 18, 2013 at 12:36 AM Report #499516 Posted March 18, 2013 at 12:36 AM (edited) 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 "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.
polska Posted March 18, 2013 at 01:33 AM Author Report #499518 Posted March 18, 2013 at 01:33 AM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 18, 2013 at 01:42 AM Report #499519 Posted 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. IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
mogers Posted March 18, 2013 at 01:53 AM Report #499520 Posted March 18, 2013 at 01:53 AM (edited) 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 "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.
polska Posted March 18, 2013 at 02:00 AM Author Report #499521 Posted March 18, 2013 at 02:00 AM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
polska Posted March 18, 2013 at 01:06 PM Author Report #499538 Posted March 18, 2013 at 01:06 PM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 18, 2013 at 02:23 PM Report #499540 Posted 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 IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted March 18, 2013 at 06:08 PM Author Report #499583 Posted 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 ... Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 18, 2013 at 06:42 PM Report #499590 Posted 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. IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted March 19, 2013 at 01:53 AM Author Report #499617 Posted 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? Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 19, 2013 at 09:31 AM Report #499622 Posted March 19, 2013 at 09:31 AM sim IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted March 20, 2013 at 03:40 PM Author Report #499769 Posted March 20, 2013 at 03:40 PM (edited) 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 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 20, 2013 at 03:44 PM Report #499770 Posted March 20, 2013 at 03:44 PM vês como não era complicado 😉 1 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now