Jump to content
Sign in to follow this  
msmsms

quicksort - ordenar um array

Recommended Posts

msmsms

quando tentei executar o programa quicksort dá-me um erro e não devolve o array ordenado. o erro que dá na consola é este:

Original array:

1, 4, 2, 3, 7, 6

Ordered array:

-1477939653, -1075083132, -1075083124, 0, 0, 0

podem-me dizer o que se passa? que reparação tenho de fazer no código para que este passe a devolver o array ordenado como é suposto?

#include <stdio.h>
#include <stdlib.h>
/* Swach values o and d */
void swap(int *o, int *d){
 int t;
 t = *o;	 /* Insert in t the value pointed by o */
 *o = *d;	 /* o points to the same value as d */
 *d = t;	 /* d points to t */
}
/* Partition array and return the indice of the particion */
int partition(int s[], int l, int h){
 int i;
 int firsthigh;
 firsthigh = l;
 for (i = l; i < h; i++)   /* Go through the array */
if (s[i] < s[h]){	/* If the velue is lower than the last position */
  swap(&s[i], &s[firsthigh]); /* Swap the values of the positions in the array */
  firsthigh++;	 /* Increases the index of the first element */
}
 swap(&s[h], &s[firsthigh]);  /* Insert the value of the next key */
 return firsthigh;
}
/* s: array to quicksort */
/* l: lower index of the array */
/* h: higher index of the array */
int quicksort(int s[], int l, int h){
 int p;
 if ((h-l) > 0){	 /* If the number of member is higher than 1 */
p = partition(s, l, h);   /* Find the index for the partition */
quicksort(s, l, p-1);   /* Sort the lower values */
quicksort(s, p+1, h);   /* Sort the higher values */
 }
 return 0;
}

/* Print the array s (n elements) in the screen */
void print_array(int s[], int n){
 int i;
 for (i = 0; i < n-1; i++){
printf("%d, ", s[i]);
 }
 printf("%d\n", s[n-1]);
}
int main(void){
 int x[] = {1, 4, 2, 3, 7, 6};

 /* Print original array */
 printf("Original array:\n");
 print_array(x,sizeof(x)/sizeof(int));

 /* Sort array */
 quicksort(x,0, sizeof(x)-1);

 /* Print sorted array */
 printf("Ordered array:\n");
 print_array(x,sizeof(x)/sizeof(int));

 return 0;
}

Edited by msmsms

Share this post


Link to post
Share on other sites
HappyHippyHippo
 quicksort(x,0, sizeof(x)-1); // olha para o último valor que estás a passar
                              // que valor é e qual deveria ser ?
                              // porque é que nas chamadas de print_array tens diferente ?


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

Share this post


Link to post
Share on other sites
msmsms

 quicksort(x,0, sizeof(x)-1); // olha para o último valor que estás a passar
						   // que valor é e qual deveria ser ?
						   // porque é que nas chamadas de print_array tens diferente ?

eu não sei, o código deve ter sido feito pelo meu professor

ai a ficha pede para compilar e executar o programa, dizendo que vou obter um array ordenado, mas não acontece isso!

eu consultei a wikipedia e achei lá o algoritmo em c do quicksort que ele deve ter usado para montar este programa fazendo a ordenação para um array e imprimindo um novo array ordenado só que não está a fazer isso...

eu penso que o que está a ser devolvido são os locais da memoria ou assim e não os valores...

Edited by msmsms

Share this post


Link to post
Share on other sites
HappyHippyHippo

o operador sizeof retorna o tamanho de memória do operando, logo, ao ter:

int x[] = {1, 4, 2, 3, 7, 6};

o tamanho de memória de x é :

sizeof(int) * <6 espaços do array> => 4 * 6 = 24 (em 32bits) ou 8 * 6 = 48 (em 64bits)

como vez, a chamada do quicksort é a mesma coisa que se tivesse:

quicksort(x, 0, 23);

que está errado porque o array não tem 24 espaços

para corrigir, basta aplicar o mesmo métodos usado na chamada da função print_array

quicksort(x,0, sizeof(x)/sizeof(int)-1);

que podes facilmente comprovar com as mesmas contas efectuadas anteriormente:

(sizeof(int) * <6 espaços do array>) / sizeof(int) => (4 * 6) / 4 = 6 (em 32bits) ou (8 * 6) / 8 = 6 (em 64bits)

nota : a razão da subtracção na chamada da função é porque estás a passar um índice do subarray a ser ordenado e não o número de elementos do array

  • Vote 1

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

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  

×
×
  • Create New...

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.