Algorithms in a Nutshell

Insertion Sort | 63

Sorting

Algorithms

Thush>(n/2)*(log(n)–1). What does this mean? Well, givennelements to be

sorted, there will be at least one path from the root to a leaf of sizeh, which

means that an algorithm that sorts by comparison requires at least this many

comparisons to sort thenelements. Note thathis computed by a functionf(n);

here in particular,f(n)=(1/2)*n*log(n)–n/2, which means that any sorting algo-

rithm using comparisons will require on the order of O(nlogn) comparisons to

sort. In the later section “Bucket Sort,” we present an alternative sorting algo-

rithm that does not rely solely on comparing elements, and can therefore achieve

better performance under specific conditions.

Common Input

For each sorting algorithm, we assume the input resides in memory, either as a

value-based contiguous block of memory or an array of pointers that point to the

elements to be sorted. For maximum generality, we assume the existence of a

comparison functioncmp(p,q), as described earlier.

Insertion Sort

In the card game Bridge, each player is dealt 13 cards, all face down. One way to

arrange a hand is to pick up the cards one at a time and insert each card into the

hand. The invariant to maintain is that the cards in the hand are always sorted by

suit and then by rank within the same suit. Start by picking up a single card to

form a hand that is (trivially) already sorted. For each card picked up, find the

correct place to insert the card into the hand, thus maintaining the invariant that

the cards in the hand are sorted. When all the cards are placed, the invariant

establishes that the algorithm works. When you hold cards in your hand, it is easy

to insert a card into its proper position because the other cards are just pushed

aside a bit to accept the new card. When the collection is stored in memory,

however, a sorting algorithm must do more work to manually move information,

in order to open up space for an element to be inserted.

The pseudocode in Figure 4-6 describes how INSERTIONSORTrepeatedly invokes

theinserthelper function to ensure thatA[0,i] is properly sorted; eventually,i

reaches the rightmost element, sortingAentirely. Figure 4-7 shows how INSER-

TIONSORToperates on a small, unordered collectionAof sizen=16. The 15 rows

that follow depict the state ofAafter each pass.Ais sorted “in place” by incre-

mentingpos=1 up ton–1 and inserting the elementA[pos] into its rightful

position in the growing sorted regionA[0,pos], demarcated on the right by a bold

vertical line. The elements shaded in gray were shifted to the right to make way

for the inserted element; in total, INSERTIONSORTexecuted 60 transpositions (a

movement of just one place by an element).

Context

Use INSERTIONSORTwhen you have a small number of elements to sort or the

elements in the initial collection are already “nearly sorted.” Determining when

the array is “small enough” varies from one machine to another and by program-

ming language. Indeed, even the type of element being compared may be

significant.

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