Algorithms in a Nutshell

(^60) | Chapter 4: Sorting Algorithms
encodings, such as UTF-16, to represent each individual character using up to
four bytes. The Unicode Consortium (www.unicode.org) has developed a sorting
standard (known as “the collation algorithm”) that handles the wide variety of
ordering rules found in different languages and cultures (Davis and Whistler,
2008).
For the algorithms presented in this chapter we assume the existence of a compar-
ator function, calledcmp, which compares elementsptoqand returns 0 ifp=q,a
negative number ifp<q, and a positive number ifp>q. If the elements are complex
records, thecmpfunction might only compare a “key” value of the elements. For
example, an airport terminal has video displays showing outbound flights in
ascending order of the destination city or departure time while flight numbers
appear to be unordered.
Stable Sorting
When the comparator functioncmpdetermines that two elementsaiandajin the
original unordered collection are equal, it may be important to maintain their rela-
tive ordering in the sorted set; that is, ifi<j, then the final location foraimust be
to the left of the final location foraj. Sorting algorithms that guarantee this prop-
erty are considered to bestable. For example, the top of Figure 4-4 shows an
original collectionAof flight information already sorted by time of flight during
the day (regardless of airline or destination city). If this collectionAis sorted using
a comparator function,cmpDestination, that orders flights by destination city, one
possible result is shown on the bottom of Figure 4-4.
Figure 4-4. Stable sort of airport terminal information
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use