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

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.

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.

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;
}

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

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.

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

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.

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.

Edited 2 Years Ago by Ancient Dragon

This article has been dead for over six months. Start a new discussion instead.