[C] Sorting an array and preserving the original index

[frodo_jedi]

Hello everybody,
I strongly need an help please!

I want to sort an array in C using a good algorithm (ex. quicksort), but at the same time I want to get for each element of the ordered array its original index in the non ordered array.

Do you have the code or suggestion please?


HELP!

Thanks in advance

[laserlight]

Instead of sorting the array, sort an array of pointers to the elements of the array, except that the comparison is done by comparing the objects that the pointers point to. When you are done, you can obtain the original indices by subtracting the pointer to the first element of your original array from each pointer in the sorted array of pointers.

[frodo_jedi]

Oh..thank you very much for answering.

Sorry but I have not understood completely what you mean ;-(

Have I to use qsort calling it on array of pointers?

Can you please explain me with few lines of code? Just an example please.

Thanks for the patience

[laserlight]

Have I to use qsort calling it on array of pointers?

Yes, you could use qsort() for this.

Can you please explain me with few lines of code? Just an example please.

Something like this:

/* Suppose that elements is the original array
   and pointers is the array of corresponding pointers.
   Suppose also that size is the size of the original array.
   Let cmp be the comparison function for qsort(). */
qsort(pointers, size, sizeof(pointers[0]), cmp);

/* Print the indices corresponding to the original array elements. */
for (size_t i = 0; i < size; ++i)
{
    printf("%u ", pointers[i] - elements);
}

EDIT:
Whoops, thinking about it further, there is no need to divide, hence I have updated my previous post.

[frodo_jedi]

Thanks a lot.
I think that another good solution is to define a struct with 2 fields: the array element (on which is made the comparation) and the index.

Thanks a lot

[laserlight]

I think that another good solution is to define a struct with 2 fields: the array element (on which is made the comparation) and the index.

Yes, it would be a good solution if the original array's elements are not expensive to copy and you really do want to sort them instead of just finding out where they would be if they were sorted.

[frodo_jedi]

Hi,
I tried to implement my idea....but does not work. There is surely a problem in the comparison function of the qsort. Can you have a look please to the following simple program?
I want to order an array of a new type (defined in the typedef), which has 2 fields: a float (the elements that I want to order) and an int (the index of the original array)

Thanks in advance

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

[laserlight]

I tried to implement my idea....but does not work. There is surely a problem in the comparison function of the qsort.

How does it not work?

[frodo_jedi]

No ;-(
Have you tried to run it?
Look at the result in the console please.

I get this:

array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 0
array_amplitudes[i].amplitude = 1.000000, array_amplitudes[i].index = 1
array_amplitudes[i].amplitude = 2.000000, array_amplitudes[i].index = 2
array_amplitudes[i].amplitude = 3.000000, array_amplitudes[i].index = 3
array_amplitudes[i].amplitude = 4.000000, array_amplitudes[i].index = 4
array_amplitudes[i].amplitude = 5.000000, array_amplitudes[i].index = 5
array_amplitudes[i].amplitude = 6.000000, array_amplitudes[i].index = 6
array_amplitudes[i].amplitude = 7.000000, array_amplitudes[i].index = 7
array_amplitudes[i].amplitude = 8.000000, array_amplitudes[i].index = 8
array_amplitudes[i].amplitude = 9.000000, array_amplitudes[i].index = 9


array_amplitudes[i].amplitude = 4.000000, array_amplitudes[i].index = 1077936128
array_amplitudes[i].amplitude = 2.000000, array_amplitudes[i].index = 1065353216
array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 3
array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 1
array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 0
array_amplitudes[i].amplitude = 5.000000, array_amplitudes[i].index = 5
array_amplitudes[i].amplitude = 6.000000, array_amplitudes[i].index = 6
array_amplitudes[i].amplitude = 7.000000, array_amplitudes[i].index = 7
array_amplitudes[i].amplitude = 8.000000, array_amplitudes[i].index = 8
array_amplitudes[i].amplitude = 9.000000, array_amplitudes[i].index = 9


Thanks for the patience

[laserlight]

Notice how I demonstrated the use of qsort() in post #4:

qsort(pointers, size, sizeof(pointers[0]), cmp);

Compare it with your own use of qsort() here:

qsort(array_amplitudes, length_array_range, sizeof(t_amplitude_index *), (void *)compare_structs);

You are taking the sizeof the wrong thing, and you are casting a function pointer to void when it is unnecessary (and wrong). You should write:

qsort(array_amplitudes, length_array_range, sizeof(array_amplitudes[0]), compare_structs);

Also, although your compare_structs function does indeed cover all possible cases, it would still be better to write it such that it becomes even more obvious that all control paths will return a value:

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;

}

[frodo_jedi]

THANK YOU VERY MUCH!!!!!

I have no words to thank you.

Now the code works perfectly:

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

This is the result


array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 0
array_amplitudes[i].amplitude = 1.000000, array_amplitudes[i].index = 1
array_amplitudes[i].amplitude = 2.000000, array_amplitudes[i].index = 2
array_amplitudes[i].amplitude = 3.000000, array_amplitudes[i].index = 3
array_amplitudes[i].amplitude = 4.000000, array_amplitudes[i].index = 4
array_amplitudes[i].amplitude = 5.000000, array_amplitudes[i].index = 5
array_amplitudes[i].amplitude = 6.000000, array_amplitudes[i].index = 6
array_amplitudes[i].amplitude = 7.000000, array_amplitudes[i].index = 7
array_amplitudes[i].amplitude = 8.000000, array_amplitudes[i].index = 8
array_amplitudes[i].amplitude = 9.000000, array_amplitudes[i].index = 9


array_amplitudes[i].amplitude = 9.000000, array_amplitudes[i].index = 9
array_amplitudes[i].amplitude = 8.000000, array_amplitudes[i].index = 8
array_amplitudes[i].amplitude = 7.000000, array_amplitudes[i].index = 7
array_amplitudes[i].amplitude = 6.000000, array_amplitudes[i].index = 6
array_amplitudes[i].amplitude = 5.000000, array_amplitudes[i].index = 5
array_amplitudes[i].amplitude = 4.000000, array_amplitudes[i].index = 4
array_amplitudes[i].amplitude = 3.000000, array_amplitudes[i].index = 3
array_amplitudes[i].amplitude = 2.000000, array_amplitudes[i].index = 2
array_amplitudes[i].amplitude = 1.000000, array_amplitudes[i].index = 1
array_amplitudes[i].amplitude = 0.000000, array_amplitudes[i].index = 0



THANKS A LOT!