Searching
Five basic kinds of sorting algorithms are available to the programmer:
In an insertion sort, you pick up the cards one at a time, starting with the top card in the pile, and insert them into the correct position in your hand. When you have picked up all the cards, they are sorted. In an exchange sort, you pick up the top two cards. If the one on the left belongs after the one on the right, you exchange the two cards’ positions. Then you pick up the next card and perform the compare on the two rightmost cards and (if needed) exchange their positions. You repeat the process until all the cards are in your hand. If you didn’t have to exchange any cards, the deck is sorted. Otherwise, you put down the deck and repeat the entire procedure until the deck is sorted. In a selection sort, you search the deck for the lowest card and pick it up. You repeat the process until you are holding all the cards.
To perform a merge sort, you deal the deck into 52 piles of one card each. Because each pile is ordered
(remember, there’s only one card in it), if you merge adjacent piles, keeping cards in order, you will have 26
ordered piles of 2 cards each. You repeat so that you have 13 piles of 4 cards, then 7 piles (6 piles of 8 cards
and 1 pile of 4 cards), until you have 1 pile of 52 cards.
In a distribution (or radix) sort, you deal the cards into 13 piles, placing each rank on its own pile. You then
pick up all the piles in order and deal the cards into 4 piles, placing each suit on its own pile. You put the
four piles together, and the deck is sorted.
There are several terms you should be aware of when examining sorting algorithms. The first is natural.
A sort is said to be natural if it works faster (does less work) on data that is already sorted, and works slower
(does more work) on data that is more mixed up. It is important to know whether a sort is natural if the data
you’re working with is already close to being sorted.
A sort is said to be stable if it preserves the ordering of data that are considered equal by the algorithm.
Consider the following list:
If this list is sorted by last name using a stable sort, “Mary Jones” will remain before “Tom Jones” in the sorted
list because they have the same last name. A stable sort can be used to sort data on a primary and secondary
key, such as first and last names (in other words, sorted primarily by last name, but sorted by first name for
entries with the same last name). This action is accomplished by sorting first on the secondary key, then on
the primary key with a stable sort.
A sort that operates on data kept entirely in RAM is an internal sort. If a sort operates on data on disk, tape,
or other secondary storage, it is called an external sort.
Five basic kinds of sorting algorithms are available to the programmer:
- Insertion sorts
- Exchange sorts
- Selection sorts
- Merge sorts
- Distribution sorts
In an insertion sort, you pick up the cards one at a time, starting with the top card in the pile, and insert them into the correct position in your hand. When you have picked up all the cards, they are sorted. In an exchange sort, you pick up the top two cards. If the one on the left belongs after the one on the right, you exchange the two cards’ positions. Then you pick up the next card and perform the compare on the two rightmost cards and (if needed) exchange their positions. You repeat the process until all the cards are in your hand. If you didn’t have to exchange any cards, the deck is sorted. Otherwise, you put down the deck and repeat the entire procedure until the deck is sorted. In a selection sort, you search the deck for the lowest card and pick it up. You repeat the process until you are holding all the cards.
To perform a merge sort, you deal the deck into 52 piles of one card each. Because each pile is ordered
(remember, there’s only one card in it), if you merge adjacent piles, keeping cards in order, you will have 26
ordered piles of 2 cards each. You repeat so that you have 13 piles of 4 cards, then 7 piles (6 piles of 8 cards
and 1 pile of 4 cards), until you have 1 pile of 52 cards.
In a distribution (or radix) sort, you deal the cards into 13 piles, placing each rank on its own pile. You then
pick up all the piles in order and deal the cards into 4 piles, placing each suit on its own pile. You put the
four piles together, and the deck is sorted.
There are several terms you should be aware of when examining sorting algorithms. The first is natural.
A sort is said to be natural if it works faster (does less work) on data that is already sorted, and works slower
(does more work) on data that is more mixed up. It is important to know whether a sort is natural if the data
you’re working with is already close to being sorted.
A sort is said to be stable if it preserves the ordering of data that are considered equal by the algorithm.
Consider the following list:
- Mary Jones
- Mary Smith
- Tom Jones
- Susie Queue
If this list is sorted by last name using a stable sort, “Mary Jones” will remain before “Tom Jones” in the sorted
list because they have the same last name. A stable sort can be used to sort data on a primary and secondary
key, such as first and last names (in other words, sorted primarily by last name, but sorted by first name for
entries with the same last name). This action is accomplished by sorting first on the secondary key, then on
the primary key with a stable sort.
A sort that operates on data kept entirely in RAM is an internal sort. If a sort operates on data on disk, tape,
or other secondary storage, it is called an external sort.
No comments:
Post a Comment