Sorting and keeping track of indexes in struct

Question

Let's say we have n number of houses. This is a house:

struct Casa {
    int id;
    int membri;
};

I am reading the size of the struct and each struct's membri from a txt file. The first value is the size of the struct (n).

I increment the ID when reading from file:

void citire(Casa house[], int n, std::ifstream & file) {

    for (int i = 0; i < n; i++)
    {
        file >> house[i].membri;
        house[i].id = i + 1;
    }
}

How do I output the houses's ID's in ascending order based on membri ?

For example:

id: 1 - membri: 2
id: 2 - membri: 8
id: 3 - membri: 6
id: 4 - membri: 10
id: 5 - membri: 4

should output:

id: 1 - membri: 2
id: 5 - membri: 4
id: 3 - membri: 6
id: 2 - membri: 8
id: 4 - membri: 10

This is what I've tried and it doesn't work and I can't see why:

void sortareSelectie(int v[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (v[j] < v[min]) min = j;
        }
        // swap
        temp = v[min];
        v[min] = v[i];
        v[i] = temp;
    }
}

void sort(Casa house[], int n) {
    int v[10], key[10];
    for (int i = 0; i < n; i++) {
        v[i] = house[i].membri;
    }

    sortareSelectie(v, n);

    for (int i = 0; i < n; i++) {
        std::cout << "Membri: " << v[i] << " - ID: " << house[i].id << std::endl;
    }
    
}

I've seen examples with vectors, with structs, with arrays.
How to obtain the index permutation after the sorting
keeping track of the original indices of an array after sorting in C
Sorting array and saving the old index in C++
Get the indices of an array after sorting?
https://www.geeksforgeeks.org/keep-track-of-previous-indexes-after-sorting-a-vector-in-c-stl/

I still don't understand how can I apply that on my example.
The thing is that I don't want and can't use use vectors, lambdas or any predefined sort function that the programming language can have.
Yes, this is for school.

I am sorry, but I am oblivious on how this works.

You would use [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort) and write the short `comp()` function to tell `std::sort` to sort on the `membri` field of he struct. — David C. Rankin, Dec 12 '20 at 08:41
Then look how sort it's implemented and copy it. Don't reinvent the wheel. — JHBonarius, Dec 12 '20 at 08:46
Oops I apologize, does that include C `qsort()`? That's another quick robust option. Otherwise a selection sort, or insertion sorts are /t quite as bad as bubble-short. If you have less than 10,000 struct to sort -- they it really doesn't matter, bubble sort, etc. would be fine. — David C. Rankin, Dec 12 '20 at 08:47
I do not know how. That is the point of this question ! I have no idea how do implement it even after looking it up. — Jorje12, Dec 12 '20 at 08:47
@DavidC.Rankin I need to it "manually". I am not allowed to use pre-defined functions. — Jorje12, Dec 12 '20 at 08:47
It looks like your sortareSelectie is sorting the membri but youre not maintaining the relationship between the membri and the id. Youre not too far off - instead of using the int v[] you need to use house[] and compare using house[j].membri < house[min].membri — ComplexityAverse, Dec 12 '20 at 08:49
@ComplexityAdverse Can you please write a working example ? I am not kidding when I say that I can't get it through my head. — Jorje12, Dec 12 '20 at 08:52
Im sorry, but it only gets harder than this. I recommend taking a break and/or starting from scratch. — ComplexityAverse, Dec 12 '20 at 08:57
I get the feeling that these answers are skipping over something. If you are learning to sort an array of Struct, you wont have used Templates, ampersands, or asterisks yet. You likely arent asking how to sort an array, rather how to sort an array of simple objects based on one member of that object. If that is the case, I found this after sorting through all the other sort() solutions. http://www.cplusplus.com/forum/beginner/98359/ — ComplexityAverse, Dec 13 '20 at 10:12

David C. Rankin · Accepted Answer · 2020-12-12T09:35:32.887

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.

score 0 · Answer 2 · answered Dec 12 '20 at 08:58

0

I would suggest you to use Hashtables. Below is the code for the question u have asked.

#include<bits/stdc++.h>
using namespace std;

int main(){
    map<int,int> mymap;
    int n;
    cin >>n;
    for(int i=0;i<n;i++){
        int temp;
        cin >> temp;
        mymap.insert({temp,i+1});
    }
    auto itr= mymap.begin();
    while(itr!=mymap.end()){
        cout << "id: "<<(*itr).second<< " - membri: "<<(*itr).first<<endl;
        itr++;
    }
}

answered Dec 12 '20 at 08:58

Milinda Reddy

11
1

Unfortunately, I can't use maps, vectors, etc. Only simple arrays and manually written functions. – Jorje12 Dec 12 '20 at 09:02
May be u could try writing whole code for merge sort and use it. – Milinda Reddy Dec 12 '20 at 09:04

score 0 · Answer 3 · answered Dec 12 '20 at 09:22

Changing your selection sort to a generic one:

template <typename T, typename Less>
void sortareSelectie(T v[], std::size_t n, Less less) {
    for (std::size_t i = 0; i + 1 < n; i++) {
        std::size_t min = i;
        for (std::size_t j = i + 1; j < n; j++) {
            if (less(v[j], v[min])) min = j;
        }
        std::swap(v[min], v[i]);
    }
}

Then

bool LessByMembri(const Casa& lhs, const Casa& rhs) { return lhs.membri < rhs.membri; } 

void sortAndPrint(Casa houses[], int n) {
    sortareSelectie(houses, n, LessByMembri);

    for (int i = 0; i < n; i++) {
        std::cout << "Membri: " << houses[i].membri << " - ID: " << houses[i].id << std::endl;
    }
    
}

Sorting and keeping track of indexes in struct

3 Answers3