How can I get the sorting permutation of an array?

Question

I have an array of k integers that I want to sort from largest to smallest integer. However, I would like it to "remember" the original index of the unsorted array. (Note: I am programming in C language).

In my example, I have an array of 26 elements which represents the occurrences of the letters of the alphabet in a text file. So, the first element is the number of times that "a" appears in the text, the second element is the number of times that "b" appears, and so on...

I want to order the array in such a way to have that I can get the statistics of occurrences of the letters from the most common to the least common.

Now, I have thought of two possible ways of doing this:

1. Using a 26x2 bidimensional array which has the indexes of the letters in the first column and the occurrences in the second column. By sorting only by the second column, I would get a 26x2 array that is ordered as I want it to be, but I don't know if the indexes would still be associated to the occurrences of the letters as well (I don't know how to implement this).

2. The other option I was thinking about is to somehow generate the permutation of the 26 indexes which WOULD sort the array without actually sorting it. In this way I could compare this "permutation array" to my unordered array and figure out which letter is the most common. However I don't know if such a function exists in C.

Could someone elighten me on how they would tackle this problem? Even with pseudo-code, as long as you let me know how the functions are called and the libraries where they are defined. Thank you so much!

Answer 1

For 26 small integers, the computation time and resources are generally negligible, so the code should be written for simplicity and clarity. If qsort accepted a context that it passed to the comparison routines, I would suggest sorting an array of indices into the count array. However, this requires knowing where the count array is, which we cannot pass through qsort. An alternative is to sort pointers to the counts:

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


#define N   26


//  Compare the counts of the letters pointed to indirectly.
static int compare(const void *va, const void *vb)
{
    const int * const *pa = va, * const *pb = vb;
    int a = **pa, b = **pb;
    return
        a <  b ? -1 :
        a == b ?  0 :
                 +1;
}


int main(void)
{
    srand(0);

    int count[N];
    for (size_t i = 0; i < N; ++i) count[i] = rand();

    //  Initialize an array of pointers into count.
    int *pointer[N];
    for (size_t i = 0; i < N; ++i) pointer[i] = &count[i];

    //  Sort the pointers.
    qsort(pointer, N, sizeof *pointer, compare);

    //  Print the letters and their counts in order from the sorted pointers.
    for (size_t i = 0; i < N; ++i)
        printf("%c appears %d times.\n",
            (int) ('a' + (pointer[i] - count)), *pointer[i]);
    //  (ASCII is assumed.)
}

Observe that, because pointer[i] points into the count array, we can recover the index of the letter using pointer[i] - count. (Bonus points for explaining why 'a' + (index[i] - count) is cast to int.)

Answer 2

You do use an array of structures with the count and the letter and sort this array with a appropriate comparison function.

Alternately, you can combine the count and the letter into a single number:

int a[26];
...

for (int i = 0; i < 26; i++) {
    a[i] = a[i] * 26 + i;
}

You can then sort this array of int, and print the counts along with the letter value:

qsort(a, 26, sizeof(*a), cmp_int);

for (i = 0; i < 26; i++) {
    printf("%c: %d\n", 'A' + a[i] % 26, a[i] / 26);
}

The comparison function for sorting in descending order:

int cmp_int(const void *a, const void *b) {
    int aa = *(const int **)a;
    int bb = *(const int **)b;
    return (aa < bb) - (aa > bb);
}

Answer 3

You can do this with a variation of the first option.

Define a struct which contains two fields: a count and the letter in question for that count. Create an array of these structs with the letters in order and populate the counts. Then sort the array of structs based on the count field. You'll be left with the structs ordered by count instead of by letter.