[C] Ordinare un array in C e portarsi dietro l'indice

[frodo_jedi]

Ciao a tutti,
ho bisogno di ordinare un array in modo efficiente (magari usando quicksort per esempio),
ma al tempo stesso ho bisogno di portarmi dietro l´indice della posizione di ogni elemento
nell´array originale disordinato.

C´é qualcuno che ha suggerimenti?
Il codice C dsarebbe il massimo... ;-)

HELP!


Vi ringrazio

[oregon]

Cosa non sai fare?

[frodo_jedi]

Ciao,
grazie per avermi risposto. Quello che non so é trovare un algoritmo
giá pronto che implementi un ordinamento che si porto dietro l´indice
e mi sono rivolto a voi per sapere se qualcuno ha giá risolto il problema


Aveter qualche suggerimento? Non so dove sbattere la testa ;-(

[oregon]

Non esiste un "algoritmo" particolare ...

Usa un normale ordinamento e man mano che ordini gli elementi, memorizzi i valori degli indici originali in un vettore parallelo ...

Prova a scrivere il codice che ordina i dati e poi si passa ad esaminare il problema degli indici ...

[frodo_jedi]

Ciao,
grazie per la risposta.
Non posso fare cosí perché deve essere altamente efficiente l´ordinamento.

Hai percaso qualche altra idea?

Grazie

[oregon]

Che vuol dire?

Usa un quick-sort e quando scambi gli elementi, scambi anche quelli del vettore parallelo degli indici originali.

[frodo_jedi]

ciao,
credo che la soluzione migliore (ora provo) sia definire una struct con 2 campi: l´indice e l´elemento dell´array.
Poi si usa qsort definendo l´ oppportuna funzione di confronto.

Ciao!

[oregon]

Originariamente inviato da frodo_jedi
credo che la soluzione migliore (ora provo) sia definire una struct con 2 campi: l´indice e l´elemento dell´array.
Poi si usa qsort definendo l´ oppportuna funzione di confronto.

Piu' che altro credi che sia meglio seguire l'indicazione di Marco in

http://www.p2pforum.it/forum/showthread.php?t=375584

che condivido, anche se il vettore parallelo e' praticamente la stessa cosa ...

Detto questo, qualsiasi strada tu segua, come ti ho gia' detto, scrivi il codice per l'ordinamento e parti da quello ...

[frodo_jedi]

Ciao,
ho provato a fare come mi ha suggerito Marco in quell´altro forum ma deve esserci un problema nella comparison function del qsort.

Potresti dare un occhi a questo semplice programma per favore?
Voglio ordinare un array di t_amplitude_index, un nuovo tipo che ha un float (l'elemento che voglio ordinare) e un int (l' indice che va preservato).

Non capisco cosa sbaglio ;-(

Help!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct _amplitude_index{ // Struct to store and order the values of the amplitudes preserving the index in the original array
    float amplitude;
    int index;
} t_amplitude_index;

int compare_structs (const void *a, const void *b);
   



int main (int argc, const char * argv[]) {

    int length_array_range = 10;
    t_amplitude_index *array_amplitudes;
    array_amplitudes = (t_amplitude_index *) malloc(sizeof(t_amplitude_index) * length_array_range);
   
    int i;
    for(i = 0; i< length_array_range;i++){
        array_amplitudes[i].amplitude = (float)i;
        array_amplitudes[i].index = i;
    }
   
    for(i = 0; i< length_array_range;i++){
    printf("array_amplitudes[i].amplitude = %f, array_amplitudes[i].index = %d\n",array_amplitudes[i].amplitude,array_amplitudes[i].index);
    }
   
   
    qsort(array_amplitudes, length_array_range, sizeof(t_amplitude_index *), (void *)compare_structs);
   
    printf("\n\n");
    for(i = 0; i< length_array_range;i++){
        printf("array_amplitudes[i].amplitude = %f, array_amplitudes[i].index = %d\n",array_amplitudes[i].amplitude,array_amplitudes[i].index);
    }
   
    free(array_amplitudes);
   
    return 0;
}



int compare_structs (const void *a, const void *b){
   
    t_amplitude_index *struct_a = (t_amplitude_index *) a;
    t_amplitude_index *struct_b = (t_amplitude_index *) b;

    //return (int)(struct_a->amplitude > struct_b->amplitude) - (struct_a->amplitude < struct_b->amplitude);// ascending order   
    //return (int)(struct_a->amplitude < struct_b->amplitude) - (struct_a->amplitude > struct_b->amplitude);// descending order   

     if(struct_a->amplitude < struct_b->amplitude) return 1;
     if(struct_a->amplitude == struct_b->amplitude) return 0;
     if(struct_a->amplitude > struct_b->amplitude) return -1;
     
}

[frodo_jedi]

Ho capito!
Avevo fatto degli errori nell´uso di qsort (sizeof e void):

ecco il codice funzionante:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct _amplitude_index{ // Struct to store and order the values of the amplitudes preserving the index in the original array
	float amplitude;
	int index;
} t_amplitude_index;

int compare_structs (const void *a, const void *b);
	



int main (int argc, const char * argv[]) {

	int length_array_range = 10;
	t_amplitude_index *array_amplitudes;
	array_amplitudes = (t_amplitude_index *) malloc(sizeof(t_amplitude_index) * length_array_range);
	
	int i;
	for(i = 0; i< length_array_range;i++){
		array_amplitudes[i].amplitude = (float)i;
		array_amplitudes[i].index = i;
	}
	
	for(i = 0; i< length_array_range;i++){
	printf("array_amplitudes[i].amplitude = %f, array_amplitudes[i].index = %d\n",array_amplitudes[i].amplitude,array_amplitudes[i].index);
	}
	
	
	qsort(array_amplitudes, length_array_range, sizeof(array_amplitudes[0]), compare_structs);
	
	printf("\n\n");
	for(i = 0; i< length_array_range;i++){
		printf("array_amplitudes[i].amplitude = %f, array_amplitudes[i].index = %d\n",array_amplitudes[i].amplitude,array_amplitudes[i].index);
	}
	
	free(array_amplitudes);
	
    return 0;
}

int compare_structs(const void *a, const void *b){
	
    t_amplitude_index *struct_a = (t_amplitude_index *) a;
    t_amplitude_index *struct_b = (t_amplitude_index *) b;
	
    if (struct_a->amplitude < struct_b->amplitude) return 1;
    else if (struct_a->amplitude == struct_b->amplitude) return 0;
    else return -1;
	
}