I have started reading Part 2 of Introduction to Algorithms and in the section The structure of the data the author/authors says in the context of sorting a sequence of numbers:
In practice, the numbers to be sorted are rarely isolated values. Each
is usually part of a collection of data called a record. Each record
contains a key, which is the value to be sorted, and the remainder of
the record consists of satellite data, which are usually carried
around with the key. In practice, when a sorting algorithm permutes
the keys, it must permute the satellite data as well. If each record
includes a large amount of satellite data, we often permute an array
of pointers to the records rather than the records themselves in order
to minimize data movement.
Can some one explain what the authors mean here ? Why the term satellite data ? What is the intuition behind this concept ? And also how this concept relates to a higher level programming platform like Java ?
Best Answer
It sounds like the authors are referring to complex data structures. In object-oriented languages, like Java, the data structure would be an object that contains a number of fields. In a language like C, the structure would probably be a
struct. When you sort, you might only care about sorting by a particular field. The other fields are satellite data - they are part of the structure, but aren't relevant to the sorting algorithms.When you sort, you can't break the structure. If you have a collection of people with the attributes of a name, a current address, a social security number, and an age and you want to sort them by age, you can't change the association between the four fields. You just need to sort them within the structure based on the value of a field. In this example, age is the key and the satellite data is the name, address, and social security number.