Ordenação Array de Estruturas

[carloscorreia94]

Boa Tarde pessoal do PAP.

Sou estudante do Instituto Superior Técnico no 1º ano e esta é a minha pequena a apresentação.

Estou a fim de entregar um projeto de Programação em C e estou com dificuldades na parte final do programa.

O meu problema consiste na ordenação de um vetor de estruturas quando este tem que ser imprimido na consola.

Usando o algoritmo de quicksort consigo ordenar o meu array por apenas um field da estrutura, mas o que é pedido é: Se pagamentosA=pagamentosB então ordena por numero de sócio, ou seja ter dois critérios de ordenação, um precedente ao outro.

A minha ideia para fazer isto foi no define da função de partição do quicksort alterar o less para isto:

#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))

Vou apresentar aqui o código da estrutura e da função de partição do quicksort. Não sei o que esteja mal, mas ele não ordena de facto a array como quero...

(Já agora, não consigo alterar o tipo de codigo para C, e ele não me mete as cores ai...)

typedef struct {
int num;
char nome[tamanho_nome];
char apelido[tamanho_apelido];
int despesas;
int pagamentos;
int meses;
int modalidades[numero_modalidades];
} associado;
//Inicio do algoritmo de quicksort
#define key(A) (A.meses)
#define key3(A) (A.num)
#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))
#define compexch(A, B) if (less(B, A)) exch(A, B)
#define exch(A, B) { associado t = A; A = B; B = t; }
int partition(associado a[], int l, int r)
{
int i = l-1;
    int j = r;

    while(i < j)
    {
            while(less(a[++i],a[r]));
            while(less(a[r],a[--j]))
            {
                    if(j == l)
                            break;
            }
            if(i < j)
                    exch(a[i], a[j]);
    }
    exch(a[i],a[r]);
    return i;
}
void quicksort(associado a[], int l, int r,int tipo)
{
//Tipo: 0 -> Ordena segundo divida, 1-> Ordena segundo numero de associado
    int i;
    if(r <= l)
            return;
if(tipo==0) { i = partition(a,l,r); }
if(tipo==1) { i = partition2(a,l,r); }    
    quicksort(a,l,i-1,tipo);
    quicksort(a,i+1,r,tipo);
}
//Fim do algoritmo de quicksort

Se alguem puder dar uma ajuda agradeco! Obrigado 😉

Edited March 29, 2013 at 03:32 PM by thoga31
GeSHi

[ffunenga]

Deixo aqui os detalhes em que reparei:

Tens que melhorar a indentação... não uses tabs ('\t'), usa antes 4 espaços.

Os defines e includes ficam melhor no inicio do codigo;

O terceiro if da função quicksort tem "partition2" como função, é um erro certo?

O parametro tipo da função quicksort podia ser antes uma variavel do tipo:

enum {DEBT, ASSOCIATE}

Cheira-me que o define exch "dá buraco". Talvez te safes melhor com:

void exch(associado *array, int i, int j) {
associado *tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

EDIT:

Agora que olho melhor para este código, isto não funciona no teu caso pq tens um array de struct's e não de apontadores. De qq das formas, eu analisva melhor esse swap.

Edited March 29, 2013 at 03:52 PM by ffunenga
GeSHi

[carloscorreia94]

Obrigado pela tua resposta pronta. O partition 2 não é um erro, aponta para outra ordenação que preciso de fazer, mas que está bem. Em relação ao enum, ainda não falei nesse código, por isso não o posso usar. Em relação a apontadores, pointers right? ainda não falamos nisso e é suposto usarmos um array de structs mesmo. Por isso como é que eu consigo contornar esta situação? obrigado!

[pmg]

Apaga os #defines do teu código e faz funções a sério.

Em alternativa, não uses "side-effects" em expressões que vão ser usadas em macros.

No teu código

while(less(a[++i],a[r]));

a variavel i vai ser actualizada mais do que uma vez dentro da expansão da macro.

PS: Esta é uma razões que fizeram nascer a norma de usar TUDO EM MAISCULAS para macros: para chamar a atenção que são macros e por o programador de sobre-aviso sobre eventuais "side-effects".

Compara o teu código com o que eu (não) escreveria

while (LESS(a[++i], a[r])) /* void */;

Edited March 29, 2013 at 07:29 PM by pmg

[carloscorreia94]

Já percebi onde estava o erro, mas não consigo concretizar uma função de modo a que o ++i não se repita :/

[pmg]

Com uma função em vez duma macro, o ++i não se repete

/* nao testado */
#include <stdio.h>
#define EXAMPLE(A, B) ((A)/((A) + (B)))
int example(int a, int b) { return a / (a + b); }
int main(void) {
 int i;
 int j;
 i = 42; j = 64;
 printf("EXAMPLE: %d\n", EXAMPLE(i++, j));
 printf("i tem %d\n", i);
 i = 42; j = 64;
 printf("example: %d\n", example(i++, j));
 printf("i tem %d\n", i);
 return 0;
}

Edited March 29, 2013 at 08:27 PM by pmg

[carloscorreia94]

Não estou a conseguir associar essa função de exemplo ao less. Se eu tirar o ++i de dentro dos argumentos da função do less e tentar incrementar o i apenas uma vez de outra maneira não tenho sucesso. Essa é a unica forma possivel que estou a ver neste momento.

[pmg]

Em vez de

#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))

faz uma função propriamente dita

int less(int A, int B) {
return ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)));
}