Mastering Algorithms With C - Kyle Loudon [130]
Binary search
An efficient search method that relies on sorted data. Binary search works fundamentally by dividing a sorted set of data repeatedly and inspecting the element in the middle of each division.
Directory listings (illustrated in this chapter)
Listings of files in a file system that have been organized into groups. Generally, an operating system will sort a directory listing in some manner before displaying it.
Database systems
Typically, large systems containing vast amounts of data that must be stored and retrieved quickly. The amount of data generally stored in databases makes an efficient and flexible approach to searching the data essential.
Spell checkers (illustrated in this chapter)
Programs that check the spelling of words in text. Validation is performed against words in a dictionary. Since spell checkers frequently deal with long strings of text containing many thousands of words, they must be able to search the set of acceptable words efficiently.
Spreadsheets
An important part of most businesses for managing inventory and financial data. Spreadsheets typically contain diverse data that is more meaningful when sorted.
Description of Insertion Sort
Insertion sort is one of the simplest sorting algorithms. It works like the approach we might use to systematically sort a pile of canceled checks by hand. We begin with a pile of unsorted checks and space for a sorted pile, which initially contains no checks. One at a time, we remove a check from the unsorted pile and, considering its number, insert it at the proper position among the sorted checks. More formally, insertion sort takes one element at a time from an unsorted set and inserts it into a sorted one by scanning the set of sorted elements to determine where the new element belongs. Although at first it may seem that insertion sort would require space for both the sorted and unsorted sets of data independently, it actually sorts in place.
Insertion sort is a simple algorithm, but it is inefficient for large sets of data. This is because determining where each element belongs in the sorted set potentially requires comparing it with every other element in the sorted set thus far. An important virtue of insertion sort, however, is that inserting a single element into a set that is already sorted requires only one scan of the sorted elements, as opposed to a complete run of the algorithm. This makes insertion sort efficient for incremental sorting . This situation might occur, for example, in a reservation system of a large hotel. Suppose one display in the system lists all guests, sorted by name, and is updated in real time as new guests check in. Using insertion sort, resorting requires only a single sweep of the data to insert a new name into the list.
Interface for Insertion Sort
Name
issort
Synopsis
int issort(void *data, int size, int esize, int (*compare)(const void *key1,
const void *key2));
Return Value
0 if sorting is successful, or -1 otherwise.
Description
Uses insertion sort to sort the array of elements in data. The number of elements in data is specified by size. The size of each element is specified by esize. The function pointer compare specifies a user-defined function to compare elements. This function should return 1 if key1 > key2, if key1 = key2, and -1 if key1 < key2 for an ascending sort. For a descending sort, compare should reverse the cases returning 1 and -1. When issort returns, data contains the sorted elements.
Complexity
O (n 2), where n is the number of elements to be sorted.
Implementation and Analysis of Insertion Sort
Insertion sort works fundamentally by inserting elements from an unsorted set one at a time into a sorted set. In the implementation presented here, both of these sets reside in data, a single block of contiguous storage. Initially, data contains the unsorted set consisting of size elements. As issort runs, data gradually becomes consumed by the sorted set until when issort returns,