# quicksort - ordenar um array

## Recommended Posts

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 on other sites
``` 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 on other sites

``` 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 on other sites

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

• 1

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

## Create an account

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...