Sorting a list with qsort?

Question

Hello. I'm writing a program in which you enter words via the keyboard or file and then they come out sorted by length. I was told I should use linked lists, because the length of the words and their number aren't fixed.

should I use linked lists to represent words?

struct node{
    char c;
    struct node *next;
};

And then how can I use qsort to sort the words by length? Doesn't qsort work with arrays?

I'm pretty new to programming.

Thank you.

Answer 1

If you know how you want the items sorted, you should use an insertion sort when reading the data so that once all the input has been entered, all you have to do is write the output. Using a linked list would be ok, though you'll find that it has O(N²) performance. If you store the input in a binary tree ordered by length (a balanced tree would be best), then your algorithm will have O(NlogN) performance. If you're only going to do it once, then go for simplicity of implementation over efficiency.

Pseudocode:

  list = new list
  read line
  while not end of file
      len = length(line)
      elem = head(list)
      while (len > length(elem->value))
          elem = elem->next
      end
      insert line in list before elem
      read line
  end

 // at this point the list's elements are sorted from shortest to longest
 // so just write it out in order
 elem = head(list)
 while (elem != null)
     output elem->value
     elem = elem->next
 end

Answer 2

There are lots of ways to handle it... You can use arrays, via dynamic memory allocation, with realloc, if you feel brave enough to try.

The standard implementation of qsort, though, needs each element to be a fixed length, which would mean having an array-of-pointers-to-strings.

Implementing a linked list, though, should be easy, compared to using pointers to pointers.

I think what you were told to do was not to save the strings as list; but in a linked list:

struct node {
    char *string;
    node *next;
}

Then, all you have to do is, every time you read a string, add a new node into the list, in its ordered place. (Walk the list until the current string's length is greater than the string you just read.)

The problem of words not being a fixed length is common, and it's usually handled by storing the world temporarily in a buffer, and then copying it into a proper length array (dynamically allocated, of course).

Edit:

In pseudo code:

array = malloc(sizeof(*char))
array_size = 1
array_count = 0

while (buffer = read != EOF):
    if(array_count == array_size)
        realloc(array, array_size * 2)
    array_count++
    sring_temp = malloc(strlen(buffer))
    array[array_count] = string_temp

qsort(array, array_count, sizeof(*char), comparison)

print array

Of course, that needs a TON of polishing. Remember that array is of type char **array, ie "A pointer to a pointer to char" (which you handle as an array of pointers); since you're passing pointers around, you can't just pass the buffer into the array.

Answer 3

Hi Dimitar :)

Yes, the classic "C" library function qsort() only works on an array. That is a contiguous collection of values in memory.

Tvanfosson advice is pretty good - as you build the linked list, you can insert elements at the correct position. That way, the list is always sorted.

I think the comment you made that you were told to use a linked list is interesting. Indeed a list can be a good data structure to use in many instances, but it does have draw backs; for example, it must be traversed to find elements.

Depending on your application, you may want to use a hash table. In C++ you could use a hash_set or a hash_map.

I would recommend you you spend some time studying basic data structures. Time spent here will server you will and better put you in a position to evaluate advice such as "use a linked list".

Answer 4

I think there is a bigger issue than the sorting algorithm which you should pick. The first of these is that the struct that you're defining is actually not going to hold a list of words, but rather a list of single letters (or a single word.) Strings in C are represented as null-terminated arrays of characters, laid out like so:

| A | n | t | h | o | n | y | \0 |

This array would ideally be declared as char[8] - one slot for each letter, plus one slot for the null byte (literally one byte of zeros in memory.)

Now I'm aware you probably know this, but it's worth pointing this out for clarity. When you operate on arrays, you can look at multiple bytes at a time and speed things up. With a linked list, you can only look at things in truly linear time: step from one character to the next. This is important when you're trying to do something quickly on strings.

The more appropriate way to hold this information is in a style that is very C like, and used in C++ as vectors: automatically-resized blocks of contiguous memory using malloc and realloc.

First, we setup a struct like this:

struct sstring {
    char *data;
    int logLen;
    int allocLen;
};
typedef struct string sstring;

And we provide some functions for these:

// mallocs a block of memory and holds its length in allocLen
string_create(string* input); 

// inserts a string and moves up the null character
// if running out of space, (logLen == allocLen), realloc 2x as much
string_addchar(string* input, char c);

string_delete(string* input);

Now, this isn't great because you can't just read into an easy buffer using scanf, but you can use a getchar()-like function to get in single characters and place them into the string using string_addchar() to avoid using a linked list. The string avoids reallocation as much as possible, only once every 2^n inserts, and you can still use string functions on it from the C string library!! This helps a LOT with implementing your sorts.

So now how do I actually implement a sort with this? You can create a similar type intended to hold entire strings in a similar manner, growing as necessary, to hold the input strings from the console. Either way, all your data now lives in contiguous blocks of memory that can be accessed as an array - because it is an array! For example, say we've got this:

struct stringarray {
    string *data;
    int logLen;
    int allocLen;
};
typedef struct stringarray cVector;
cVector myData;

And similar functions as before: create, delete, insert.

The key here is that you can implement your sort functions using strcmp() on the string.data element since it's JUST a C string. Since we've got a built-in implementation of qsort that uses a function pointer, all we have to do is wrap strcmp() for use with these types and pass the address in.

Answer 5

You qsort a linked list by allocating an array of pointers, one per list element.

You then sort that array, where in the compare function you are of course receiving pointers to your list elements.

This then gives you a sorted list of pointers.

You then traverse your list, by traversing the array of pointers and adjusting each element in turn. rearranging its order in the list to match the order of your array of pointers.