write an algorithm for inserting card in a list
Answers
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 Insertion Sort repeatedly invokes the insert helper function to ensure that A[0,i] is properly sorted; eventually, i reaches the rightmost element, sorting A entirely. Figure 4-7 shows how Insertion Sort operates on a small, unordered collection A of size n=16. The 15 rows that follow depict the state of A after each pass. A is sorted "in place" by incrementing pos=1 up to n−1 and inserting the element A[pos] into its rightful position in the growing sorted region A[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, Insertion Sort executed 60 transpositions (a movement of just one place by an element).
Insertion Sort fact sheet
Figure 4-6. Insertion Sort fact sheet
The progression of Insertion Sort on a small array
Figure 4-7. The progression of Insertion Sort on a small array
Context
Use Insertion Sort when 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 programming language. Indeed, even the type of element being compared may be significant.
Forces
Insertion Sort need only set aside space for a single element to function properly. For a pointer-based representation, this is trivial; for a value-based representation, one need only allocate enough memory to store a value (requiring a fixed s bytes, as described in the earlier section "Representation") for the duration of the sort, after which it can be freed. There are no complicated nested loops to implement, and a generic function can be written to sort many different types of elements simply through the use of a cmp comparator function. For value-based representations, most language libraries offer a block memory move function to make the algorithm more efficient.
Solution
When the information is stored using pointers, the C program in Example 4-1 sorts an array ar with items that can be compared using a provided comparison function, cmp.
Example 4-1. Insertion Sort with pointer-based values
void sortPointers (void **ar, int n,
int(*cmp)(const void *,const void *)) {
int j;
for (j = 1; j < n; j++) {
int i = j-1;
void *value = ar[j];
while (i >= 0 && cmp(ar[i], value)> 0) {
ar[i+1] = ar[i];
i--;
}
ar[i+1] = value;
}
}
When A is represented using value-based storage, it is packed into n rows of a fixed element size of s bytes. Manipulating the values requires a comparison function as well as the means to copy values from one location to another. Example 4-2 shows a suitable C program that uses memmove to transfer the underlying bytes efficiently for a set of contiguous entries in A.