Mastering Algorithms With C - Kyle Loudon [136]
* *
*****************************************************************************/
*dir = NULL;
count = 0;
while ((curdir = readdir(dirptr)) != NULL) {
count++;
if ((temp = (Directory *)realloc(*dir, count * sizeof(Directory))) ==
NULL) {
free(*dir);
return -1;
}
else {
*dir = temp;
}
strcpy(((*dir)[count - 1]).name, curdir->d_name);
}
closedir(dirptr);
/*****************************************************************************
* *
* Sort the directory entries by name. *
* *
*****************************************************************************/
if (qksort(*dir, count, sizeof(Directory), 0, count - 1, compare_dir) != 0)
return -1;
/*****************************************************************************
* *
* Return the number of directory entries. *
* *
*****************************************************************************/
return count;
}
Description of Merge Sort
Merge sort is another example of a divide-and-conquer sorting algorithm (see Chapter 1). Like quicksort, it relies on making comparisons between elements to sort them. However, it does not sort in place.
Returning once again to the example of sorting a pile of canceled checks by hand, we begin with an unsorted pile that we divide in half. Next, we divide each of the resulting two piles in half and continue this process until we end up with one check in every pile. Once all piles contain a single check, we merge the piles two by two so that each new pile is a sorted combination of the two that were merged. Merging continues until we end up with one big pile again. At this point, the checks are sorted.
As with quicksort, since merge sort is a divide-and-conquer algorithm, it is helpful to consider it more formally in terms of the three steps common to all divide-and-conquer algorithms:
Divide: we divide the data in half.
Conquer: we sort the two divisions by recursively applying merge sort to them.
Combine: we merge the two divisions into a single sorted set.
The distinguishing component of merge sort is its merging process. This is the process that takes two sorted sets and merges them into a single sorted one. As we will see, merging two sorted sets is efficient because we need only make one pass through each set. This fact, combined with the predictable way the algorithm divides the data, makes merge sort in all cases as good as the average case of quicksort.
Unfortunately, the space requirement of merge sort presents a drawback. Because merging cannot be performed in place, merge sort requires twice the space of the unsorted data. This significantly reduces its desirability in the general case since we can expect to sort just as fast using quicksort, without the extra storage requirement. However, merge sort is nevertheless valuable for very large sets of data because it divides the data in predictable ways. This allows us to divide the data into more manageable pieces ourselves, use merge sort to sort them, and then perform as many merges as necessary without having to keep the entire set of data in memory all at once.
Interface for Merge Sort
Name
mgsort
Synopsis
int mgsort(void *data, int size, int esize, int i, int k, int (*compare)
(const void *key1, const void *key2));
Return Value
0 if sorting is successful, or -1 otherwise.
Description
Uses merge 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 arguments i and k define the current division being sorted and initially should be and size - 1, respectively. The function pointer compare specifies a user-defined function to compare elements. It should perform in a manner similar to that described for issort. When mgsort returns, data contains the sorted elements.
Complexity
O (n lg n), where n is the number of elements to be sorted.
Implementation and Analysis of Merge Sort
Merge sort works fundamentally by recursively dividing an unsorted set of elements into single-element