A String Example: Sorting Strings

I l @ ve RuBoard

A String Example: Sorting Strings

Let's tackle the practical problem of sorting strings alphabetically . This task can show up in preparing name lists, in making up an index, and in many other situations. One of the main tools in such a program is strcmp() , because it can be used to determine the order of two strings. The general plan will be to read an array of strings, sort them, and print them. A little while ago, we presented a scheme for reading strings, and we will start the program that way. Printing the strings is no problem. We'll use a standard sorting algorithm that we'll explain later. We will do one slightly tricky thing; see whether you can spot it. Listing 11.25 presents the program.

Listing 11.25 The sort_str.c program.

 /* sort_str.c -- reads in strings and sorts them */ #include <stdio.h> #include <string.h> #define SIZE 81        /* string length limit, including 
  /* sort_str.c -- reads in strings and sorts them */ #include <stdio.h> #include <string.h> #define SIZE 81 /* string length limit, including \0 */ #define LIM 20 /* maximum number of lines to be read */ #define HALT "" /* null string to stop input */ void stsrt(char *strings[], int num);/* string-sort function */ int main(void) { char input[LIM][ SIZE ]; /* array to store input */ char *ptstr[LIM]; /* array of pointer variables */ int ct = 0; /* input count */ int k; /* output count */ printf("Input up to %d lines, and I will sort them.\n",LIM); printf("To stop, press the Enter key at a line's start.\n"); while (ct < LIM && gets(input[ct]) != NULL && input[ct][0] != `\0') { ptstr[ct] = input[ct]; /* set ptrs to strings */ ct++; } stsrt(ptstr, ct); /* string sorter */ puts("\nHere's the sorted list:\n"); for (k = 0; k < ct; k++) puts(ptstr[k]) ; /* sorted pointers */ return 0; } /* string-pointer-sorting function */ void stsrt(char *strings[], int num) { char *temp; int top, seek; for (top = 0; top < num-1; top++) for (seek = top + 1; seek < num; seek++) if (strcmp(strings[top],strings[seek]) > 0) { temp = strings[top]; strings[top] = strings[seek]; strings[seek] = temp; } }  
 */ #define LIM 20         /* maximum number of lines to be read */ #define HALT ""        /* null string to stop input          */ void stsrt(char *strings[], int num);/* string-sort function */ int main(void) {   char input[LIM][SIZE];       /* array to store input       */   char *ptstr[LIM];            /* array of pointer variables */   int ct = 0;                  /* input count                */   int k;                       /* output count               */   printf("Input up to %d lines, and I will sort them.\n",LIM);   printf("To stop, press the Enter key at a line's start.\n");   while (ct < LIM && gets(input[ct]) != NULL                               && input[ct][0] != ` 
  /* sort_str.c -- reads in strings and sorts them */ #include <stdio.h> #include <string.h> #define SIZE 81 /* string length limit, including \0 */ #define LIM 20 /* maximum number of lines to be read */ #define HALT "" /* null string to stop input */ void stsrt(char *strings[], int num);/* string-sort function */ int main(void) { char input[LIM][ SIZE ]; /* array to store input */ char *ptstr[LIM]; /* array of pointer variables */ int ct = 0; /* input count */ int k; /* output count */ printf("Input up to %d lines, and I will sort them.\n",LIM); printf("To stop, press the Enter key at a line's start.\n"); while (ct < LIM && gets(input[ct]) != NULL && input[ct][0] != `\0') { ptstr[ct] = input[ct]; /* set ptrs to strings */ ct++; } stsrt(ptstr, ct); /* string sorter */ puts("\nHere's the sorted list:\n"); for (k = 0; k < ct; k++) puts(ptstr[k]) ; /* sorted pointers */ return 0; } /* string-pointer-sorting function */ void stsrt(char *strings[], int num) { char *temp; int top, seek; for (top = 0; top < num-1; top++) for (seek = top + 1; seek < num; seek++) if (strcmp(strings[top],strings[seek]) > 0) { temp = strings[top]; strings[top] = strings[seek]; strings[seek] = temp; } }  
 ')   {      ptstr[ct] = input[ct];    /* set ptrs to strings        */      ct++;   }   stsrt(ptstr, ct);            /* string sorter              */   puts("\nHere's the sorted list:\n");   for (k = 0; k < ct; k++)      puts(ptstr[k]) ;          /* sorted pointers            */   return 0; } /* string-pointer-sorting function */ void stsrt(char *strings[], int num) {   char *temp;   int top, seek;   for (top = 0; top < num-1; top++)      for (seek = top + 1; seek < num; seek++)         if (strcmp(strings[top],strings[seek]) > 0)         {             temp = strings[top];             strings[top] = strings[seek];             strings[seek] = temp;         } } 

We fed Listing 11.22 an obscure nursery rhyme to test it:

 Input up to 20 lines, and I will sort them. To stop, press the Enter key at a line's start.  O that I was where I would be,   Then would I be where I am not;   But where I am I must be,   And where I would be I can not.  

Here's the sorted list:

 And where I would be I can not. But where I am I must be, O that I was where I would be, Then would I be where I am not; 

Hmm, the nursery rhyme doesn't seem to suffer much from being alphabetized.

The tricky part of the program is that instead of rearranging the strings themselves , we just rearranged pointers to the strings. Let us explain. Originally, ptrst[0] is set to input[0] , and so on. That means the pointer ptrst[i] points to the first character in the array input[i] . Each input[i] is an array of 81 elements, and each ptrst[] is a single variable. The sorting procedure rearranges ptrst , leaving input untouched. If, for example, input[1] comes before input[0] alphabetically, the program switches ptrsts , causing ptrst[0] to point to the beginning of input[1] and causing ptrst[1] to point to the beginning of input[0] . This is much easier than using, say, strcpy () to interchange the contents of the two input strings. See Figure 11.5 for another view of this process.

Figure 11.5. Sorting string pointers.

Sorting

To sort the pointers, we use the selection sort algorithm. The idea is to use a for loop to compare each element in turn with the first element. If the compared element precedes the current first element, the program swaps the two. By the time the program reaches the end of the loop, the first element contains a pointer to whichever string is first in the machine collating sequence. Then the outer for loop repeats the process, this time starting with the second element of input . When the inner loop completes, the pointer to the second-ranking string ends up in the second element of ptrst . The process continues until all the elements have been sorted. We'll take a more detailed look at this algorithm in Chapter 13, "Storage Classes and Program Development."

I l @ ve RuBoard