sorting a text file

[hariza]

Hi guys,

If i have a file like the one below what would be the best/easiest way to sort the words in alphabetical order. thanks.

with
an
equal
mix
of
biosolids
to
make
the
compost
Sawdust
is
on
their
greens
Compost
applied
properly
will
enhance
growth
of
grass
flowers
shrubs
by
improving
the

[Ancient Dragon]

c or c++? read all the words into an array of strings then use either C's qsort() function or c++ sort(). If you are required to write your own sort routine then you can't use either of those functions. in that case, google for "sort algorithms" and you will find quite a few of them. Bubble Sort is the easiest to code but can be the slowest to execute.

[Micko]

If you need to write sort code, I would recommend insertion sort.
Read this:
http://www.eternallyconfuzzled.com/tuts/sorting.html

[WaltP]

If you need to write sort code, I would recommend insertion sort.
Read this:
http://www.eternallyconfuzzled.com/tuts/sorting.html

Not me. I'd use a bubble sort. The list is short. The sort is easy. Start with the easiest and when comfortable, move up to the harder ones.

[Micko]

I disagree. Many people thinks bubble sort is easiest just because it is usually first sort algorithm teached in many books and classrooms. It's performance are bad for large lists and it's much better in my opinion to get used to better algorithms. Insertion sort is more natural and i don't see why it is harder to understand comparing with bubble sort.

[Ancient Dragon]

for very small amounts of data it doesn't really matter what althrithm is used.

Keep in mind that "best" depends on your situation - the quick sort may look like the fastest sort, but using it to sort a list of 20 items is kind of like going after a fly with a sledgehammer.

[~s.o.s~]

But still given that the worst sorting time for "Quicksort" equals the time complexity of bubble sort, so it does no harm in using the fastest algorithm out there, just to keep the algo common independent of the data fed into it.

The below link is interesting to look at :
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm

[Ene Uran]

If you use C++, load a string vector and use the vector's sort. Then you don't have to give a rat-poop about the sorting algorithm, it will be the best! A somewhat modern example:

// load a string vector with words from a whitespace 
// separated text file and sort the words

/* typical sample file:
with
an
equal
mix
of
biosolids
to
make
the
compost
*/

#include <string>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() 
{
  vector<string> sV;
  ifstream in("compost.txt");
  string word;
  
  // separates words in file at a whitespace
  // and loads a string vector
  while(in >> word)
    sV.push_back(word);
     
  cout << "Unsorted words:" << endl;
  for(int i = 0; i < sV.size(); i++)
    cout << sV[i] << endl;
  
  cout << "---------------" << endl;
    
  cout << "Sorted words:" << endl;
  sort( sV.begin(), sV.end() );
  for(int i = 0; i < sV.size(); i++)
    cout << sV[i] << endl;  
  
  cin.get();
  return 0;
}

[~s.o.s~]

Yeah i agree with Mr. Ene Uran. The inbuilt vector sort function is much more sophisticated compared to the normal sort functions in terms of both performance and interface.

The STL implementation of sort, however, uses the introsort algorithm whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.

Look here:http://www.sgi.com/tech/stl/sort.html

[Inanna]

If i have a file like the one below what would be the best/easiest way to sort the words in alphabetical order.

Whatever way the system/compiler offers. :) If you just need the file sorted beforehand, I don't know of an OS that doesn't give you an easy to use sort program from the command prompt. If you need to sort the file at runtime from your program, both C and C++ have good and easy to use sorting functions.

Not me. I'd use a bubble sort. The list is short. The sort is easy.

The list was an example, I think. hariza said the file was like the one pasted, so it could be a complete dictionary. Bubble sort would choke on somethin' like that. :) I'd prolly use Shell sort as a first draft, then somethin' harder if it's not good enough.

[vegaseat]

For something like a dictionary sized array of strings I would use a combination of sorting routines with look-ahead. Something Narue's snippet "Optimized quicksort implementation" shows:
http://www.daniweb.com/code/snippet61.html

I did a comparison of simple sorting routines and came up with this:
Sorting an integer array (50000 random integers) -->
qsort() = 31ms shellsort = 922ms insertionsort = 2672ms bubblesort = 12032ms
see: http://www.daniweb.com/code/snippet377.html

[gaurav23]

what could we do if theirare more than 10000000000 words?

[Gonbe]

what could we do if theirare more than 10000000000 words?

We could then ask this on Daniweb by bumping a 6 year old thread after which we could demolish our computer never to touch one ever again.

[Sebastian_2]

Great :)

[Ancient Dragon]

I don't think there are any languages with 10,000,000,000 (10 Billion) words. But if you have a file with that many random words (many duplicates I suppose) then sort it in small chuncks, save the sorted chuncks in their own files then finaly merge-sort all the files. If you sort in chuncks of 1 million words then there will be 10,000 files to merge sort.