Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.