CODEWITHSUNDEEP
calphabetical-sort
Michi
Michi

Reputation: 125

What would be the optimal way to sort a long list of words in alphabetical order in C?

As the title indicates, I need to order quite a few (hundreds of thousands) strings in alphabetical order. I have several linked lists and each linked list contains words of a specific length. That is, I have a 6 letter strings list, 7 letter strings list, ... , 10 letter strings list.

I was thinking of using radix sort, but I wanted to see if there were better options out there since I can't find anything specific when it comes to alphabetizing a list where all the words are the same length.

EDIT:

I have an extremely long list of words, raging in size. I'm currently walking through the list and arranging the words into size categories. That is, when I encounter a word of length 6 it goes into the "6-length" list. As I'm doing this for each word, I am actually creating a new word object that contains the original word and its alphabetized version (e.g. stack, ackst). I want to alphabetize each "length" list such that I could easily find and group anagrams.

Upvotes: 0

Views: 193

Answers (1)

unwind
unwind

Reputation: 400019

I don't think the fact that the lengths are the same matters to sorting, does it? You don't explain how you think that would affect sorting.

My recommended approach for sorting a linked list: don't. :) Sort an array instead, and convert to/from the linked list as needed. It will very likely be much faster and easier.

Basically:

  1. Walk the list to figure out the length.
  2. Allocate an array of value pointers (in your case, "value" means string).
  3. Walk the list again, setting the i:th array element to point to the i:th list item's data.
  4. Sort the array with qsort().
  5. Walk the list a third time, overwriting the i:th item's data with the i:th array element
  6. Done.

You can do this for each linked list separately, of course.

Upvotes: 1

Related Questions