Thread: Sorting words with a fast, effincient sorting method

  1. #1
    Unregistered
    Guest

    Question Sorting words with a fast, effincient sorting method

    Hello, I'm a newbie to the site, but a rookie programmer, sorta. What I need to do is pull in a list of words then sort them alphabetically. I have a few ideas nut I need you're help. First off I planned (but am willing to change) to use apstring, which is what we used in my computer science event in UIL, but I don't know how to get it for my home compiler. This however isn't my problem.

    Once I had the actual words I was going to go through and put all the words with A at the beginning in a array, then b's and so on (once again willing to change). Then use some sort of sorting algorithom to sort them and combine all the arrays back into one list again. Should I try and use quicksort somehow, or should I go a different route. Please note that I need this to be quick and the list of words will vary wildly, as in there might be a few hundred THOUSAND words to deal with. Thanks for all the help.

    Jordan Nickerson.

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    52
    There have been many posts concerning this issue. I would advise first using the "search" feature, then narrowing down your questions to specifics.
    MS VC++ 6.0

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    If you don't want to use the STL sorting algorithm, consider implementing a merge sort with an insertion sort when the number of items gets smaller.

    -Prelude
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    I recommend quicksort.

    Kuphryn

  5. #5
    a
    Guest
    bogo sort anyone?

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >bogo sort anyone?
    Only when no one is looking and someone else can take the blame.

    -Prelude
    My best code is written with the delete key.

  7. #7
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    I had a project which required the sorting of hundreds of thousands of words.

    For this I used quicksort. The time take it takes will depends upon the 'sortedness' of your initial word list. If the initial list is in a near sorted state, it will be done very quickly. If the list is highly unsorted, expect a lot longer (hours, maybe days).
    OS: Windows XP
    Compilers: MinGW (Code::Blocks), BCB 5

    BigAngryDog.com

  8. #8
    I'm Back
    Join Date
    Dec 2001
    Posts
    556
    Bogo Sort.. What's that?
    -

  9. #9
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    it's the easiest sort to implement, but only a "bogo" would use it.

    think: if you were Homer Simpson, and on marajuana, and on brain-killers, and drunk, and had a lot of time to spare, how would you sort a deck of cards?

  10. #10
    I'm Back
    Join Date
    Dec 2001
    Posts
    556
    Originally posted by ygfperson
    think: if you were Homer Simpson, and on marajuana, and on brain-killers, and drunk, and had a lot of time to spare, how would you sort a deck of cards?
    LOL
    -

  11. #11
    Unregistered
    Guest
    I was thinking about quicksort but do I have to modify it any to work with apstrings, or do I jsut send the array to quicksort and it handles it the same as if it were a array of numbers?

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Bogo Sort.. What's that?
    bogo-sort /boh`goh-sort'/ n.

    (var. `stupid-sort') The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say "Oh, I see, this program uses bogo-sort." Esp. appropriate for algorithms with factorial or super-exponential running time in the average case and probabilistically infinite worst-case running time. Compare bogus, brute force, lasherism.

    A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that it is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.
    -Prelude
    My best code is written with the delete key.

  13. #13
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    Originally posted by Unregistered
    I was thinking about quicksort but do I have to modify it any to work with apstrings, or do I jsut send the array to quicksort and it handles it the same as if it were a array of numbers?
    i don't know what apstrings are. but a quick-sort, properly implemented, should work fine. for simplicity, you might want to try a radix sort.

  14. #14
    a
    Guest
    doh i have been found out
    bogo sorts are funny as hell

  15. #15
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    apstring is a horrid little string container class that is used in AP comp sci classes.

    yes, an implementation that is able to sort integers should work, since all of the necesary operators are overloaded.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginners Contest #2 For those who wanted more!!
    By ILoveVectors in forum Contests Board
    Replies: 16
    Last Post: 08-12-2005, 12:03 AM
  2. sorting words
    By owi_just in forum C Programming
    Replies: 5
    Last Post: 05-27-2005, 06:31 PM
  3. Problem with malloc() and sorting words from text file
    By goron350 in forum C Programming
    Replies: 11
    Last Post: 11-30-2004, 10:01 AM
  4. New Theme
    By XSquared in forum A Brief History of Cprogramming.com
    Replies: 160
    Last Post: 04-01-2004, 08:00 PM