Arrays of Structs & Sorting
Organizing collections of records, and the two sorts you should be able to write from scratch
In a nutshell
An array of structs is how C holds a collection of records: a list of students, a list of network packets, a list of game entities. Once you have a collection, the two universal questions are “what is the smallest / largest / first matching element?” (search) and “can I see them in order?” (sort). Selection sort and bubble sort are the two algorithms worth writing by hand at this stage: both run in O(n²), both are short, and both force you to think about swapping struct values (or pointers to them).
Why it matters
In the real world you almost always use qsort (week 7) or a library. But writing a sort by hand is the clearest way to practice the three skills you need: iterating over an array of structs, comparing on a specific field, and swapping elements. Every interview-style algorithm question assumes you can do these without thinking. And the sorting discipline transfers: once you can sort students by GPA, you can sort by name, by age, by any composite field.
Key takeaways
- Sort by copying full structs, not by rebuilding the array. A swap is three assignments:
tmp = a[i]; a[i] = a[j]; a[j] = tmp;. C assigns structs by value. - Comparison lives in one place. A comparison function (or an inline
if) that comparesroster[i].gpawithroster[j].gpais the only thing that changes when you sort by a different field. - Linear search is O(n). If the array is sorted, binary search is O(log n) but requires the array to actually be sorted and indexed contiguously.
- Stable vs unstable sorts. A stable sort preserves the relative order of equal elements. Selection sort is not stable; bubble sort can be made stable. Mostly matters when you sort by one field after another.
- Swapping pointers vs swapping values. For huge structs, swap pointers to structs (cheap). For small structs, swap struct values (also cheap, and simpler).
Lessons in this topic
| Lesson | What it covers |
|---|---|
| Sorting & Searching | Selection sort and bubble sort by hand, linear vs binary search, applying them to arrays of structs |
Practice and deep dives
Practice this topic: Sorting drill, or browse the practice gallery.
What comes next
2D Arrays — rows and columns, for matrices, grids, game boards, and any problem where position in two dimensions is part of the data.