sorted array in other array, but only index

Question

I have a small problem, I have a array:

int tab[] = {7,2,6,1,8,1,5,3,7,2} //index: 0-9

And its it index = values:

0 = 7, 
1 = 2,
2 = 6,
3 = 1, 
4 = 8, 
5 = 1,
6 = 5,
7 = 3,
8 = 7,
9 = 2,

I want to have in a second array the sorted indexes of the first.

int tab2 shoud be: index = value(index of first array but sorted):

0 = 3, 
1 = 5,
2 = 1,
3 = 9, 
4 = 7, 
5 = 6,
6 = 2,
7 = 0,
8 = 8,
9 = 4,

I have a code to fast sort, but it won't sort the first array, but write a sorted index in second array.

void quicksort(int *tab, int p, int q,int *tb){
    int v=tab[p];
    int i,j,x;
    i=p;
    j=q;
    do
    {
        while(tab[i]<v) i++;
        while(tab[j]>v) j--;
        if(i<=j)
        {
            x=tab[i];
            tab[i]=tab[j];
            tab[j]=x;
            i++;
            j--;
        }
    }
    while(i<=j);
    if(j>p) quicksort(tab,p, j,tb);
    if(i<q) quicksort(tab, i, q,tb);
}

Is this something you're trying to do in C? Or C++? The two are actually quite different. — scohe001, Aug 10 '20 at 19:30
Ahh well there goes my dupe vote then. Instead take a look at [keeping track of the original indices of an array after sorting in C](https://stackoverflow.com/q/24586499/2602718) — scohe001, Aug 10 '20 at 19:32
What is the parameter `tb` good for in function `quicksort`? — M. Nejat Aydin, Aug 10 '20 at 19:35
tb is secound array, pointer for it. In this array I should have a sorted index of first array tab — quwertysokman, Aug 10 '20 at 19:44

score 0 · Accepted Answer · answered Aug 10 '20 at 19:49

If it is unimportant which sorting algorithm to use then one of simplest approaches is to use the insertion sort.

For example

#include <stdio.h>

void insertion_sort( const int a[], size_t n, size_t b[] )
{
    for ( size_t i = 0; i < n; i++ )
    {
        size_t j = i;
        
        for ( ; j != 0 && a[i] < a[b[j-1]]; --j )
        {
            b[j] = b[j-1];
        }
        
        b[j] = i;
    }
}

int main(void) 
{
    enum { N = 10 };
    int a[N] = { 7, 2, 6, 1, 8, 1, 5, 3, 7, 2 };
    size_t b[N];
    
    insertion_sort( a, N, b );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[b[i]] );
    }
    putchar( '\n' );
    
    return 0;
}

The program output is

1 1 2 2 3 5 6 7 7 8

sorted array in other array, but only index

1 Answers1