Concept
Why is it more efficient to sort pointers to structures?
ComputerScienceOne / Sorting Pointers to Elements
"Recall that it is sometimes preferable to maintain an array of pointers to structures rather than an array of structures. Sorting is a scenario where this is particularly true. When sorting an array of structure elements, the entire structure is copied back and forth as elements are swapped. Depending on the number of bytes of a structure, this can be quite expensive. It is generally more efficient to sort an array of pointers to structures instead. Another case is when we wish to sort user-defined structures. The Student structure presented earlier is “small” in that it only has a few fields. When structures are stored in an array and sorted, there may be many swaps of individual elements which involves a lot of memory copying. If the structures are small this is not too bad, but for “larger” structures this could be potentially expensive. Instead, it may be preferred to have an array of pointers to structures. Swapping elements involves only swapping pointers instead of the entire structure. This is far cheaper as a memory address is likely to be far smaller than the actual structure it points to."
Related Ideas
- How can an array of structure pointers make swapping structures more efficient?ComputerScienceOne · Arrays of Structures
- How should a comparator handle an array of structure pointers with NULL values?ComputerScienceOne · Sorting Pointers to Elements
- How do you create and use an array of structures in C?ComputerScienceOne · Arrays of Structures
- How can you combine contiguous structure storage with indirect access?ComputerScienceOne · Arrays of Structures
- How can comparator functions order Student structures?ComputerScienceOne · Comparator Functions
- How does the C standard library’s qsort() function work?ComputerScienceOne · Sorting
- What is a comparator function and how does it determine element order?ComputerScienceOne · Comparator Functions
- How do you pass an array of pointers to structures to a function?ComputerScienceOne · Passing Arrays of Structures