C++ Sorting and Keeping Track of Indexes

C - Sort float array while keeping track of indices

Use a structure to store the value as well as index and then sort according to value.

struct str
{
    float value;
    int index;
};

int cmp(const void *a, const void *b)
{
    struct str *a1 = (struct str *)a;
    struct str *a2 = (struct str *)b;
    if ((*a1).value > (*a2).value)
        return -1;
    else if ((*a1).value < (*a2).value)
        return 1;
    else
        return 0;
}

int main()
{
    float arr[3] = {0.4, 3.12, 1.7};
    struct str objects[3];
    for (int i = 0; i < 3; i++)
    {
        objects[i].value = arr[i];
        objects[i].index = i;
    }
    //sort objects array according to value maybe using qsort
    qsort(objects, 3, sizeof(objects[0]), cmp);
    for (int i = 0; i < 3; i++)
        printf("%d ", objects[i].index); //will give 1 2 0
    // your code goes here
    return 0;
}

keep track of previous indexes after sorting

I solved your problem by creating a struct which contains the actual value and the index of a given number given by the user:

typedef struct num {
    int index;
    int value;
} num_t;


void swap(num_t *xp, num_t *yp){
    num_t temp= *xp;
    *xp = *yp;
    *yp = temp;
}

void sort(num_t arr[], int n)
{
    int i, j;

    for(i = 0; i < n-1; i++)
    {
        for(j = 0; j < n - i - 1; j++)
            if(arr[j].value>arr[j+1].value)
                swap(&arr[j], &arr[j+1]);
    }
}

void print(num_t arr[],int size)
{
    int i;
    for (i = 0; i < size; i++)
    {
        printf("%d[%d] ", arr[i].value, arr[i].index);
    }
    printf("\n\n");
}

int main()
{
    int i, n;

    printf("Total number: ");
    scanf("%d", &n);

    num_t number[n];

    printf("\nInput numbers:\n");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &number[i].value);
        number[i].index = i;
    }

    for(i = 0; i < n; i++)
    {
        printf("%d[%d] ", number[i].value, number[i].index);
    }

    n = sizeof(number) / sizeof(number[0]);
    sort(number, n);

    printf("\nSorted array: ");
    print(number, n);

    return 0;
}

Sorting and keeping track of indexes in struct

There are one of a number of sorts you can choose from. The simple sorts like bubble-sort being the worst efficient, and then various selection sorts, until you get to the longer partitioning sort where efficiency finally improves.

Here a simple selection-sort example sorting your example struct ascending will do. The selection so is as easy as any other:

void insertion_sort (struct Casa *arr, size_t size)
{
    int i, j;

    for (i = 0; i < (int)size; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[j].membri > arr[j + 1].membri) {
                struct Casa tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            } else
                break;
        }
    }
}

For a descending sort based on membri you would just change the > to a < in:

            if (arr[j].membri < arr[j + 1].membri) {

Putting it altogether in a short example using your sample data, you would have:

#include <iostream>
#include <iomanip>

struct Casa {
    int id;
    int membri;
};

void insertion_sort (struct Casa *arr, size_t size)
{
    int i, j;

    for (i = 0; i < (int)size; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[j].membri > arr[j + 1].membri) {
                struct Casa tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            } else
                break;
        }
    }
}

int main (void) {
    
    struct Casa houses[] = { {1,2}, {5,4}, {3,6}, {2,8}, {4,10} };
    size_t n = sizeof houses / sizeof *houses;
    insertion_sort (houses, n);
    std::cout << n << " houses sorted by membri\n\n";
    for (size_t i = 0; i < n; i++)
        std::cout << "id: " << houses[i].id << 
                    "  mdmbri: " << std::setw(2) << houses[i].membri << '\n';
}

Example Use/Output

$ ./bin/struct_casa
5 houses sorted by membri

id: 1  mdmbri:  2
id: 5  mdmbri:  4
id: 3  mdmbri:  6
id: 2  mdmbri:  8
id: 4  mdmbri: 10

Or with the change made for a descending-sort:

$ ./bin/struct_casa
5 houses sorted by membri

id: 4  mdmbri: 10
id: 2  mdmbri:  8
id: 3  mdmbri:  6
id: 5  mdmbri:  4
id: 1  mdmbri:  2

Look things over and let me know if you have any additional questions.

c++ sort keeping track of indices [duplicate]

Using C++11, the following should work just fine:

template <typename T>
std::vector<size_t> ordered(std::vector<T> const& values) {
    std::vector<size_t> indices(values.size());
    std::iota(begin(indices), end(indices), static_cast<size_t>(0));

    std::sort(
        begin(indices), end(indices),
        [&](size_t a, size_t b) { return values[a] < values[b]; }
    );
    return indices;
}

keeping track of the original indices of an array after sorting in C

There is also a method as follows under limited conditions.

#include <stdio.h>

int main(void){
    int data[] ={ 5,4,1,2,3 }; //Without duplication, The number of limited range.
    int size = sizeof(data)/sizeof(*data);
    int keys[size];
    int i;

    printf("data :\n");
    for(i=0;i<size;i++){
        printf("%d ",data[i]);
    }
    for(i=0;i<size;i++){
        keys[data[i]-1]=i;
    }

    printf("\n\ndata\tindex\n");
    for(i=0;i<size;i++){
        printf("%d\t%d\n", data[keys[i]], keys[i]);
    }
    return 0;
}
/* result sample
data :
5 4 1 2 3

data    index
1       2
2       3
3       4
4       1
5       0
*/

---

How to sort an array of index @Kerrek is as proposed.

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

int *array;

int cmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}

int main(void){
    int data[] ={ 5,4,1,2,3 };
    int size = sizeof(data)/sizeof(*data);
    int index[size];//use malloc to large size array
    int i;

    for(i=0;i<size;i++){
        index[i] = i;
    }
    array = data;
    qsort(index, size, sizeof(*index), cmp);
    printf("\n\ndata\tindex\n");
    for(i=0;i<size;i++){
        printf("%d\t%d\n", data[index[i]], index[i]);
    }
    return 0;
}

sort array in C, return sorted indices

The problem I see is that within main function - you are allocating pointer b some memory -

   int * b = malloc(sizeof(int) * sizeof(a) / sizeof (*a));

The next line calls order_int(...) that returns a pointer to already allocated memory -

  b = order_int(a, sizeof(a) / sizeof(*a));

Looking at the order_int function -

int * order_int (const int * ARRAY, const size_t SIZE) {
    int * idx = malloc(SIZE * sizeof(int));
    base_arr = malloc(sizeof(int) * SIZE);
    for (size_t i = 0; i < SIZE; i++) {
        base_arr[i] = ARRAY[i];
        idx[i] = i;
    }
    qsort(idx, SIZE, sizeof(int), compar_increase);
    free(base_arr); base_arr = NULL;
    return idx;
}

.. you see that idx has been already been allocated the correct memory.

I would suggest removing the malloc from b - see below.

  int * b = NULL;

Sort and keep track of elements

There's no off-the-shelf functionality to achieve this, but there are work-arounds. You can, for example, keep an array of user-defined structs that also contain the original position:

A = { {4,0}, {1,1}, {5,2}, {2,3}, {3,4}}

And then sort this using a custom comparator function that sorts by the value and not the original index.

A_sorted = {{1,1}, {2,3}, {3,4}, {4,0}, {5,2}}

C++ Sort vector by index

You don't want std::sort, you want std::rotate.

    std::vector<int> v = {20, 21, 22, 23, 24, 25,
                          26, 27, 28, 29, 30, 31};
    auto b = std::next(std::begin(v), 3); // skip first three elements
    auto const re = std::end(v);  // keep track of the actual end
    auto e = std::next(b, 6);  // the end of our current block
    while(e < re) {
        auto mid = std::next(b, 3);
        std::rotate(b, mid, e);
        b = e;
        std::advance(e, 6);
    }
    // print the results
    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " "));

This code assumes you always do two groups of 3 for each rotation, but you could obviously work with whichever arbitrary ranges you wanted.

The output looks like what you'd want:

20 21 22 26 27 28 23 24 25 29 30 31

Update: @Blastfurnace pointed out that std::swap_ranges would work as well. The rotate call can be replaced with the following line:

std::swap_ranges(b, mid, mid);  // passing mid twice on purpose

---

Related Topics