sorting in a struct within a struct

[occams razor]

this one has had me stuck for a few days and I am wondering if it is my idea of what is happening here that is askew...

typedef struct node *node_ptr;

struct node {
        char *name;
        int n_students;
        struct student students[1000];
        node_ptr next;
}

struct student {
        int ID;
        char *name;
}

I have the structure working with nodes (which correspond with units the students enrol in) and they are sorted alphabetically on insertion.... but

I'm having a hard time when I insert students to figure how to insert them in order by ID. I mean given student 1 is and ID of 123 and student 2 is 155 - what should I be doing as a general strategy to insert ID 139 for example.

My strategy so far was to find the place it fit and then attempt to shuffle the rest up one and insert the student... which doesn't seem to work. Is this the wrong way. My issue is related to not understanding the rules perhaps - "can I" shuffle the rest of these struct members along and insert in the right spot or is there a trick to it?

I haven't posted code yet as I'm at this point hoping my understanding of the general idea might improve. It is also a uni assignment (although I am 42yo) and I don't particularly just want to put up code here or get out of the box answers unless I have to to gain that understanding. I somehow dont' understand this one.

could anyone offer some advice?

[MacGyver]

If your linked list is already sorted one way and you need to sort it a different way, couldn't you just dump the linked list to an array of pointers to each node, sort the array however you want it, and then rebuild the linked list? I believe a solution like this was already posted just recently.

[occams razor]

Thanks for the reply...

The student struct doesnt have a next so only the nodes (units) are a linked list. [ADDED: -- The nodes are sorted by name in ascending order, these are courses BUT each course can have many students sorted on their student ID, so its not the resorting you expected in your reply].

I'm trying to sort the students in a struct / array which is a part of a single linked list node. Next would be very handy at this point.

Another consideration is I have a Big O limitation so I probably can't afford to offload into secondary data structures unless its absolutely the only way, but thanks for the input as I hadn't really considered the option.

Obviously there must be some way to do this, for example where found is a pointer to the correct node (unit) I thought perhaps this might have worked (but it didn't) - for an insertion which is smaller than num students I would try to increment the number of the student record (kind of)... so basically all the bigger numbers might shuffle to the right and let me put in the student in the correct place.

where the appropriate spot is...
found->students[num++];

then insert the new student in the hole...

of course it didnt' work unfortunately. I'm wondering how one would actually go about inserting in order in this situation. Perhaps I do need to unload it into an array...

[occams razor]

At this point I am inserting the new student in the right place but the loop overwrites every member for the rest of the student struct... any ideas on how I might efficiently shuffle these along to fit my student in a struct without next?

any conversation on this would be appreciated, I have to admit I'm stumped at this point.

[Salem]

> these are courses BUT each course can have many students
Give it a better name than 'node' then.

> struct student students[1000];
This is simply a huge waste of space.
If this were a linked list as well, then inserting new students into the list is an easy list update, no need to move any other data about to make room.

On the other hand, an array is much easier to sort if later on you decide you want sort by name rather than sort by ID. But rather than a fixed array, use a struct student *students; and dynamically allocate what you need.

Does the array have to be sorted all the time, or can you say add all the students, then sort it once at the end?

[occams razor]

Hi Salem, thanks for replying. A constraint on the learning exprience of this exercise is for me to use the structs as defined so I never chose the [1000]. I'm just finding it hard to come to terms with the shuffling of the rest of the students right before inserting the next student.

I guess I'm getting there slowly though

[Salem]

OK then - it looks like you're "stuck" with the array shuffling then.
Which end do you shuffle from?

[occams razor]

I've tried starting from the far end but have just made myself confused... tonight I'll have to go and nut out the algorithm a bit better I think. Its dinner time here now and probably part of it is the transition from learning to hacking as I got boggled.

Hopefully tomorrow will bring some insight. Thanks again for replying and sorry I can't post code directly. I don't want to put myself in any academic hot water. I'm pretty sure I'm on the right track though although when I posted I wasn't that sure.