Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

msmsms

quicksort - ordenar um array

Mensagens Recomendadas

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

Editado por msmsms

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Editado por msmsms

Partilhar esta mensagem


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

  • Voto 1

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

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.