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 ?
2
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.
You are likely confused with popular meaning of satellite as a spacecraft. Meaning in your quote is not about space technology.
Better look up other term definitions in Wiktionary:
An attendant on an important person; a member of someone’s retinue, often in a somewhat derogatory sense; a henchman. [from 16th c.] … A moon or other smaller body orbiting a larger one. [from 17th c.]… A country, state, office, building etc. which is under the jurisdiction, influence, or domination of another body. [from 19th c.]…
Satellite data in the record from your quote refers to above meaning, where record key is considered “dominant” while the rest of the data just follows it.
Rest of the data in the record is considered less important in the context of sorting, which takes into account only the key. In sorting, it’s record key that dominates, the rest just follows it.