Re: how to efficiently do sorting and get array of indices?

From: Martin Dickopp (expires-2004-06-30_at_zero-based.org)
Date: 05/21/04 

Date: Fri, 21 May 2004 01:25:13 +0200

b83503104@yahoo.com (b83503104) writes:

> In matlab, the sort function returns two things:
>
> [a,b]=sort([5, 8, 7])
>
> a = 5 7 8
> b = 1 3 2
>
> where a is the sorted result, and b is the corresponding index.
> Is there C or C++ code available to achieve this?

The `qsort' function can be used for sorting. If you put each value and
the corresponding index together in a structure object, you can sort
them simultaneously. Write the comparison function so that it only
compares the values, but ignores the indices. See code below for an
example.

(If you're interested in the C++ answer, which is completely different,
ask in comp.lang.c++.)

Martin

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

struct pair {
    int a;
    int b;
};

int compare (const void *const first, const void *const second)
{
    if (((const struct pair *)first)->a > ((const struct pair *)second)->a)
        return 1;
    else if (((const struct pair *)first)->a < ((const struct pair *)second)->a)
        return -1;
    else
        return 0;
}

int main (void)
{
    const int array [] = {5, 8, 7};
    struct pair ab [sizeof array / sizeof *array];
    size_t i;

    for (i = 0; i < sizeof array / sizeof *array; ++i)
    {
        ab [i].a = array [i];
        ab [i].b = i + 1;
    }

    qsort (ab, sizeof ab / sizeof *ab, sizeof *ab, compare);

    fputs ("a =", stdout);
    for (i = 0; i < sizeof ab / sizeof *ab; ++i)
        printf (" %d", ab [i].a);
    fputs ("\nb =", stdout);
    for (i = 0; i < sizeof ab / sizeof *ab; ++i)
        printf (" %d", ab [i].b);
    putchar ('\n');

    return 0;
} 

-- 
   ,--.    Martin Dickopp, Dresden, Germany                 ,= ,-_-. =.
  / ,- )   http://www.zero-based.org/                      ((_/)o o(\_))
  \ `-'                                                     `-'(. .)`-'
   `-.     Debian, a variant of the GNU operating system.       \_/