[C] Sorting an array and preserving the original index

This is a discussion on [C] Sorting an array and preserving the original index within the C Programming forums, part of the General Programming Boards category; Hello everybody, I strongly need an help please! I want to sort an array in C using a good algorithm ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    7

    [C] Sorting an array and preserving the original index

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    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.
    Last edited by laserlight; 04-05-2009 at 03:06 PM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    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

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Quote Originally Posted by frodo_jedi
    Have I to use qsort calling it on array of pointers?
    Yes, you could use qsort() for this.

    Quote Originally Posted by frodo_jedi
    Can you please explain me with few lines of code? Just an example please.
    Something like this:
    Code:
    /* 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.
    Last edited by laserlight; 04-05-2009 at 03:06 PM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    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

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Quote Originally Posted by frodo_jedi
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    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

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

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Quote Originally Posted by frodo_jedi
    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?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    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

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,185
    Notice how I demonstrated the use of qsort() in post #4:
    Code:
    qsort(pointers, size, sizeof(pointers[0]), cmp);
    Compare it with your own use of qsort() here:
    Code:
    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:
    Code:
    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:
    Code:
    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;
    
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    THANK YOU VERY MUCH!!!!!

    I have no words to thank you.

    Now the code works perfectly:


    Code:
    #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!

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21