Jump to content
Larry Ullman's Book Forums

Bubble Sorting Structs


Recommended Posts

Hi,

 

I am developing a variation of Larry's script 11.6 and am having trouble understanding how to apply the pointers bubble sort in my context.

 

In a nutshell, my application reads in lines of ordinary text from a small .txt file I created.  I then read the file line by line and then parse each line for words.  I store the words in a struct:

/* Define the structure. */

struct word_store

{

 char the_word[WORD_SIZE];

 int counter;

 struct word_store *next;

 struct word_store *previous;

};

 

/* Use typedef to create an alias. */

typedef struct word_store ws;

At the moment I am not using the two pointers in the struct but I will want to use them later as I want to extend this to use a b-tree to store an array of these struct elements.

 

If the word from the line parse is already in the struct array, I increment the counter for that word; if it is not, then I add the word to the struct array with a counter value of one and add an address pointer to the array element in an array of these pointers.

 

All this works fine.

 

But when I have finished reading and parsing, I want to sort the words alphabetically and I'm trying to adapt the pointer sort example starting on page 281.

 

But the words are not getting sorted properly and I'm wondering if my strcmp is not giving me the result I expect when I compare, for example, the words 'a' and 'and'. Here's my code:

for (l = 0; l < (store_index - 1); l++)

  { // loop through each word in the store

   for (m = (l + 1); m < store_index; m++)

   { // loop through each word again

    if (strcmp(word_array[l].the_word, word_array[m].the_word) > 0)

     { // if the result is > 0, word_arry[m].the_word should come before word_array[l].the word so we need to swap their pointers

      temp_pointer = ws_pointers[l];

      ws_pointers[l] = ws_pointers[m];

      ws_pointers[m] = temp_pointer;

     } // end if

   } // end inner loop

  } // end outer loop

  

  printf("The words stored and their frequency are:\n");

  for (j = 0; j < store_index; j++)

  {

   // get the next word and put it into hold_it

   hold_it = *ws_pointers[j];

   printf("%s (%d)\n", hold_it.the_word, hold_it.counter);

  }

where store_index holds the count of the number of struct elements in the array.

 

The pointers are declared as:

ws word_array[ARRAY_SIZE]; // ARRAY_SIZE is defined in defws.h

 ws *ws_pointers[ARRAY_SIZE]; // an array of pointers to ws typedefs (word_store structs)

 ws *temp_pointer;

 ws hold_it;

The supposedly sorted words are not printing in alphabetic order.

 

My environment is Windows 7 with Dev-C++ as the IDE.

 

Any advice will be most appreciated and thanks in anticipation.

Link to comment
Share on other sites

OK, I found my error. In my sort where I compare the two words, I was not following Larry's example properly.  The strcmp should not be comparing the words directly from the array, but the words pointed to by the pointers.

 

The correct comparison in my example is:

temp_1 = *ws_pointers[l];

temp_2 = *ws_pointers[m];

rc = strcasecmp(temp_1.the_word, temp_2.the_word); // the compare ignores the case
...

And I changed it to a case insensitive compare.

 

Thanks to anyone who looked at this and pondered on a solution.

 

Cheers from Oz.

Link to comment
Share on other sites

 Share

×
×
  • Create New...