How to obtain the descending order (ordinality) of an integer array?

Question

I need to find the descending order of the elements in an array of integers.

Example:

If I have an array:

x = {24, 55, 22, 1}

I want an algorithm in C that results in array order where:

order = {2, 1, 3, 4}

Considering that 'my' array x can become rather large (from 1k-1M), my question is as follows: How do I get the order array as efficiently (fast) as possible? Clearly there must exist an efficient algorithm that does that already?

• Keith Thompson: By "vector", do you mean array? C++ has a type vector in its standard library; C does not. (gcc also has an unrelated extension called vectors, unrelated to C++'s std::vector.)
• userjuicer: I meant array of course. Sorry if I was unclear.

Answer 1

I guess the more efficient way is the best known way. Eg:

• allocate a vector for all indices from 0 up to N-1 and initialize it
• sort the indices vector by using one of the efficient sorting algorithms eg quicksort or merge sort but by referring to the original data vector (you sort indices, you compare original data)

• Filipe Gonçalves: Good answer. Just to add some additional info: this method is O(n*log(n)), and it can't get any better than that as it is bounded by the sorting operation.
• ryyker: @FilipeGonçalves - where, how were you able to determine this type of efficiency rating? (i.e. O(n*log(n)). Do you have a link?
• Filipe Gonçalves: @ryyker Well, since quicksort and mergesort both run in O(n*log(n)), that's the complexity of the whole algorithm...

Answer 2

You can use the comparator function of the qsort standard function: http://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm Just implement your comparator to add an indirection, ie replace:

return ( *(int*)a - *(int*)b );

by

return (x[*(int*)b] - x[*(int*)a]);

(edit to get descending order)

#include <stdio.h>
#include <stdlib.h>
int x[] = { 88, 56, 100, 2, 25 };
int indexes[] = { 0, 1, 2, 3, 4};
int cmpfunc (const void * a, const void * b)
{
 return ( x[*(int*)b] - x[*(int*)a] );
}
int main()
{
 int n;
 printf("Before sorting the list is: \n");
 for( n = 0 ; n < 5; n++ ) {
 printf("%d ", indexes[n]);
 }
 qsort(indexes, 5, sizeof(int), cmpfunc);
 printf("\nAfter sorting the list is: \n");
 for( n = 0 ; n < 5; n++ ) {
 printf("%d ", indexes[n]);
 }
 return(0);
}

• userjuicer: Could you possibly elaborate a bit since I didnt get it to work when I tested it on the sample code?
• userjuicer: Thanks now I understand. It always helps with an example.
• Keith Thompson: Using subtraction, like your return ( *(int*)a - *(int*)b );, in a qsort comparison function risks problems with overflow (consider if a is a large negative number and b is a large positive number).

Answer 3

I would start with qsort from stdlib.h Since it takes a pointer to function, will not be the fastest, but is surely the easier to code.

int v[4] = {24, 55, 22, 1};
int fcmp(const void *a, const void *b) {
 int A = *(const int*)a;
 int B = *(const int*)b;
 if (v[A] > v[B]) return -1;
 if (v[A] < v[B]) return +1;
 return 0;
}
int main(int argc, char *argv[])
{
 int r[4] = {0, 1, 2, 3 };
 qsort(r, 4, sizeof(int), fcmp);
}