Sort records by one field, and see stability matter on real data.
What to build
A program that lists students from the highest mark to the lowest, with a stable sort.
Requirements
- Store each student in a struct with a name and a mark.
- Sort by mark, from highest to lowest, using insertion sort.
- Students with equal marks must stay in the order they were read.
Input
The first line has n. Each of the next n lines has a name, with no spaces, and a mark.
Output
n lines, each with a name and a mark, separated by a space.
Constraints
1 ≤ n ≤ 50, names have 1 to 20 letters, and marks are from 0 to 100.
Example
Input:
4
Asha 70
Bilal 85
Chen 70
Dina 90
Output:
Dina 90
Bilal 85
Asha 70
Chen 70
Why it works
Insertion sort moves a record past another only when the mark is strictly lower. Equal marks never pass each other, so the original order among them is kept. That is what stable means.
Examples
Example 1 · Input
4 Asha 70 Bilal 85 Chen 70 Dina 90
Expected output
Dina 90 Bilal 85 Asha 70 Chen 70
Example 2 · Input
1 Omar 50
Expected output
Omar 50
Hints
Hint 1
Keep each name and mark together in one struct, and move whole structs.
Hint 2
Use insertion sort, shifting only records whose mark is strictly lower than the one being inserted.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
typedef struct {
char name[21];
int mark;
} Student;
int main(void) {
int n;
Student s[50];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%20s %d", s[i].name, &s[i].mark);
for (int i = 1; i < n; i++) {
Student key = s[i];
int j = i - 1;
while (j >= 0 && s[j].mark < key.mark) {
s[j + 1] = s[j];
j--;
}
s[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%s %d\n", s[i].name, s[i].mark);
return 0;
}