Sort other data structures

So far, we have sorted only character arrays. Obviously, the above functions can be altered to sort arrays of any of the built-in data types, simply by changing the types of parameters and variables. However, it usually becomes necessary to sort composite data types, such as strings, or aggregated data, such as structures. Most sorting tasks deal with a key and information associated with that key. To adapt algorithms for processing such data, it is necessary to modify the comparison code, the exchange code, or both. The algorithm itself does not change.

Because quick sorting is currently one of the best general-purpose sorting methods, it is used in the following examples. However, the same principle applies to all other methods described earlier.

Sort Rows

String sorting is a common programming task. Rows are easiest to sort when they are stored in a string table. The string table is just an array of strings. And an array of strings is a two-dimensional array of characters, in which the number of rows in a table is determined by the size of the left dimension, and the maximum length of the string — the size of the right dimension. (Arrays of strings were discussed in Chapter 4.) The following string version of quick sort accepts an array of strings in which the size of each string is limited to ten characters. (You can change this length if you want.) This version sorts the strings in lexicographical order.

  / * Quick sorting lines.  * /
 void quick_string (char items [] [10], int count)
 {
   qs_string (items, 0, count-1);
 }

 void qs_string (char items [] [10], int left, int right)
 {
   register int i, j;
   char * x;
   char temp [10];

   i = left;  j = right;
   x = items [(left + right) / 2];

   do {
     while ((strcmp (items [i], x) <0) && (i <right)) i ++;
     while ((strcmp (items [j], x)> 0) && (j> left)) j--;
     if (i <= j) {
       strcpy (temp, items [i]);
       strcpy (items [i], items [j]);
       strcpy (items [j], temp);
       i ++;  j--;
    }
   } while (i <= j);

   if (left <j) qs_string (items, left, j);
   if (i <right) qs_string (items, i, right);
 }

Note that the strcmp () function is now used in the comparison fragment. This function returns a negative number if the first line is lexicographically less than the second, returns zero if the lines are equal, and a positive number if the first line is lexicographically larger than the second. It should also be noted that exchanging two strings requires three calls to the strcpy () function.

Keep in mind that the strcmp () function slows down sorting for two reasons. First, a function call appears in the program, which always takes time. Secondly, the strcmp () function itself performs several comparisons to determine which of the two lines is greater. In the first case, if the speed is very important, you can put the string comparison code directly into the sort function by duplicating the function code strcmp () . In the second case, there is no way to avoid string comparison, since by definition this is exactly what is required in this task. The same reasoning applies to the strcpy () function. Exchanging two strings with strcpy () involves calling a function and exchanging the contents of strings character by character — each of these operations takes time. The overhead of calling a function can be eliminated by inserting the copy code directly into the sorting algorithm. However, the fact that exchanging two strings means exchanging individual characters (one after the other) cannot be changed.

Below is a simple main () function that demonstrates the quick-sort string quick_string () function:

  #include <stdio.h>
 #include <string.h>

 void quick_string (char items [] [10], int count);
 void qs_string (char items [] [10], int left, int right);

 char str [] [10] = {"one",
                    "two",
                    "three",
                    "four"
                  };

 int main (void)
 {
   int i;

   quick_string (str, 4);

   for (i = 0; i <4; i ++) printf ("% s", str [i]);

   return 0;
 }

Sort Structures

Most applications that use sorting provide for sorting data sets. For example, mailing lists, warehouse databases and employee journals contain sets of different types of data. As you know, in C programs, data sets are usually stored in structures. Although a structure usually contains several members, structures are usually sorted only by one member field, which is used as the sort key. With the exception of choosing a key, the methods of sorting structures are no different from the methods of sorting other types of data.

To illustrate an example of sorting structures, let's create a structure called address , in which you can store an email address. Such a structure can be used in the program mailing. The description of the address structure is shown below:

  struct address {
   char name [40];  / * name * /
   char street [40];  /* the outside */
   char city [20];  /* city */
   char state [3];  /* state */
   char zip [11];  / * index * /
 };

Since it seems reasonable to organize the address list as an array of structures, in this example, assume that the sorting procedure will sort the array of address type structures. This procedure is shown below. It sorts addresses by zip code.

  / * Quick sorting of fvkuyy structures.  * /
 void quick_struct (struct address items [], int count)
 {
   qs_struct (items, 0, count-1);
 }

 void qs_struct (struct address items [], int left, int right)
 {

   register int i, j;
   char * x;
   struct address temp;

   i = left;  j = right;
   x = items [(left + right) / 2] .zip;

   do {
     while ((strcmp (items [i] .zip, x) <0) && (i <right)) i ++;
     while ((strcmp (items [j] .zip, x)> 0) && (j> left)) j--;
     if (i <= j) {
       temp = items [i];
       items [i] = items [j];
       items [j] = temp;
       i ++;  j--;
     }
   } while (i <= j);

   if (left <j) qs_struct (items, left, j);
   if (i <right) qs_struct (items, i, right);
 }