Mastering Algorithms with C

Quicksort Example: Directory Listings

In a hierarchical file system, files are typically organized conceptually into directories. For any directory, we may want to see a list of the files and subdirectories the directory contains. In Unix, we do this with the ls command, for example. At the command prompt in Windows, we do this with the dir command.

This section presents a function called directls, which implements the same basic functionality that ls provides. It uses the system call readdir to create a listing of the directory specified in path (see Examples Example 12.3 and Example 12.4). Just as ls does in the default case, directls sorts the listing by name. Because we allocate the listing using realloc as we build it, it is the responsibility of the caller to free it with free once it is no longer needed.

The runtime complexity of directls is O (n lg n), where n is the number of entries in the directory being listed. This is because retrieving n directory entries is an operation that runs in O (n) time overall, while the subsequent call to qksort sorts the entries in O (n lg n) time.

Example 12.3. Header for Getting Directory Listings

/***************************************************************************** * * * ------------------------------ directls.h ------------------------------ * * * *****************************************************************************/ #ifndef DIRECTLS_H #define DIRECTLS_H #include <dirent.h> /***************************************************************************** ...