Computer Science Canada

string sort
Author:  Jeevan25 [ Wed Dec 21, 2005 5:09 pm ]
Post subject:  string sort
i am in need of help. i am a high school student taking c++. i am using dev c++ as my ide. i need to write a program that reades from a file. the file contains 1000 words in random order. one word per line. the program reads the file and sort the words in alphabetic order. then it outputs the sorted words to a new file. for example.
unsorted words.dat
code:
pile
game
they
apple


now the program will read this file and sort the words in alphabetic order and save to a new file.
sorted words.dat
code:
apple
game
pile
they
how do i do this? pls help. thanks.
Author:  wtd [ Wed Dec 21, 2005 5:13 pm ]
Post subject: 
Well, first you need to read the lines from the file into something like a:

c++:
std::vector<std::string>


Now, here's where you ask me what that is. Don't worry, specific questions are how you learn. Smile
Author:  Jeevan25 [ Wed Dec 21, 2005 7:42 pm ]
Post subject: 
yeap. i didnt go that far. my teacher told me three ways. select sort, insertion sort and bubble sort. i didn't learn what you typed. Very Happy my teacher ain't that great either. she tells me to come after school but she is never there.
Author:  wtd [ Wed Dec 21, 2005 7:44 pm ]
Post subject: 
Well, as I said, the first step is to get the lines into some kindof collection, then you can worry about the sort.
Author:  Martin [ Wed Dec 21, 2005 7:56 pm ]
Post subject: 
File input and output:
http://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200109/notes/io.html

How to use Vectors and arrays:
http://cplus.about.com/od/beginnerctutorial/l/aa050102a.htm

And finally, sorting. If you haven't heard of any of these, start with the bubble sort. It's horribly slow, but very easy to do and for 1000 entries will be more than fast enough.
http://en.wikipedia.org/wiki/Sort_algorithm

Your program will look something like this (assuming you're going for a functional (ie. non object oriented) approach):

1. Create a new vector.
2. Open the file.
3. Loop through the file and fill up the vector with the file's contents
4. Close the file.
5. Sort the contents of the vector.
6. Output results.
Author:  Jeevan25 [ Wed Dec 21, 2005 10:03 pm ]
Post subject: 
i need to know the loops and the if statements to sort the words. i know how to read and write to files.
Author:  bugzpodder [ Wed Dec 21, 2005 10:37 pm ]
Post subject: 
if you find the examples martin give are not enough, then I suggest you go speak to your teacher. He will be more accessible and provide more relevant help
Author:  Jeevan25 [ Wed Dec 21, 2005 10:46 pm ]
Post subject: 
yeah right. i hate her. i ask for help with my code. somthing is wrong. she ask like 3 people who are getting moer than 80 to help me because she couldn' find problem. then she called the best student. he is the one who solved it. not the teacher. if there was a worst teacher of millenium she would be that one.
Author:  wtd [ Wed Dec 21, 2005 10:51 pm ]
Post subject: 
Shame the STL can't be fully utilized.

code:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namspace std;

int main()
{
   vector<string> words;
   ifstream input_file("file_name");

   copy(istream_iterator<string>(input_file),
        istream_iterator<int>(),
        back_inserter(words));   
   sort(words);
   copy(words.begin(),
        words.end(),
        ostream_iterator<string>(cout, "\n"));

   return 0;
}
Author:  wtd [ Wed Dec 21, 2005 11:22 pm ]
Post subject: 
Hmmm... actually...

code:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namspace std;

int main()
{
   ifstream input_file("file_name");
   vector<string> words(istream_iterator<string>(input_file),
                        istream_iterator<string>());

   sort(words);
   copy(words.begin(),
        words.end(),
        ostream_iterator<string>(cout, "\n"));

   return 0;
}
Author:  MysticVegeta [ Sun Dec 25, 2005 12:59 pm ]
Post subject: 
haha I love this sort commands which are not there in Turing by the ways, But I have a question, Didn't your teacher say about "shell sort"? I think thats the fastest way to sort...

http://linux.wku.edu/~lamonml/algor/sort/sort.html
Author:  Hikaru79 [ Sun Dec 25, 2005 2:59 pm ]
Post subject: 
MysticVegeta wrote:
Didn't your teacher say about "shell sort"? I think thats the fastest way to sort...

Haha, no, it's the fastest of the O(n^2) algorithms -- that's far, far away from being faster than quicksort or merge sort (for anything other than trivially-sized lists, that is).
Author:  wtd [ Sun Dec 25, 2005 3:01 pm ]
Post subject: 
http://en.wikipedia.org/wiki/Sorting_Algorithm
Author:  MysticVegeta [ Mon Jan 02, 2006 12:06 am ]
Post subject: 
Heap sort seems to beat merge and quicksort..
Author:  Geminias [ Mon Jan 02, 2006 10:02 am ]
Post subject: 
Quote:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namspace std; //typo should be "namespace"

int main()
{
ifstream input_file("file_name");
vector<string> words(istream_iterator<string>(input_file),
istream_iterator<string>());

sort(words);
copy(words.begin(),
words.end(),
ostream_iterator<string>(cout, "\n"));

return 0;
}


if namespace were spelled right would this code compile for you wtd?
Author:  wtd [ Mon Jan 02, 2006 2:08 pm ]
Post subject: 
code:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <string>

using namespace std; //typo should be "namespace"

int main()
{
   ifstream input_file("file_name");
   vector<string> words =
      vector<string>(istream_iterator<string>(input_file),
                     istream_iterator<string>());

   sort(words.begin(), words.end());
   copy(words.begin(),
        words.end(),
        ostream_iterator<string>(cout, "\n"));

   return 0;
}


Now it compiles.
Author:  Geminias [ Tue Jan 03, 2006 12:36 am ]
Post subject: 
oh i see, you left out an equal sign too.. thats why i was getting all these errors.

I like the vector class, its cool.

One question though.. what is istream_iterator?
Author:  wtd [ Tue Jan 03, 2006 12:53 am ]
Post subject: 
The entire Standard Template Library very heavily uses iterators. It essentially is a value which represents a position in a collection.

In this case we're dealing with an input stream iterator.

code:
istream_iterator<string>(input_file)


Creates a new iterator pointing to the beginning of the input_file input stream.

code:
istream_iterator<string>()


Represents the end of the stream.
Author:  Geminias [ Tue Jan 03, 2006 1:07 am ]
Post subject: 
thanks.. it has become more clear except how do iterators differ from pointers?

and why do they use the underscore convention?

So "istream_iterator <string>" is an overloaded function and when you pass it no parameter it defaults to pointing to the end of a istream?
Author:  wtd [ Tue Jan 03, 2006 1:17 am ]
Post subject: 
Geminias wrote:
thanks.. it has become more clear except how do iterators differ from pointers?


In a lot of ways they can be used very similarly to pointers.

Geminias wrote:
and why do they use the underscore convention?


Why not? Smile

C++ forces no particular naming conventions, so it's pretty much a matter of taste. Unfortunately, lots of different libraries do things differently, so you can't really justify the use of any one convention as a means of maintaining consistency with the names from libraries.

I guess the programmers at SGI decided they liked underscores. Perhaps they also know that lowercase letters are typically easier to read than capitals, and without camelCasing, you need underscores as separators.

Geminias wrote:
So "istream_iterator <string>" is an overloaded function and when you pass it no parameter it defaults to pointing to the end of a istream?


istream_iterator is a class, actually. When you pass it no argument, you get the equivalent of a NULL pointer. Then when the STL function using the iterator is looping it basically starts with the first iterator can advances it until it equals the second iterator.

At the end of the input stream, it gets that NULL equivalent, which equals the second iterator, and that tells it to stop iterating (looping).
Author:  Geminias [ Tue Jan 03, 2006 2:48 am ]
Post subject: 
the reason i asked about the underscore was because i thought iterator was a member function of istream. i didnt realize istream_iterator was a class. I pretty much understand now. TY Wink
Author:  md [ Tue Jan 03, 2006 10:21 pm ]
Post subject: 
MysticVegeta wrote:
Heap sort seems to beat merge and quicksort..

Erm... wha? Methinks you're mistaken... Quick sort and Merge sort are the two fastest sorts given most sets of data. Heap sort is fast too, and is the same O(n log n), but in practice it ends up being slower then quick sort or merge sort.
Author:  DIIST [ Tue Jan 03, 2006 10:55 pm ]
Post subject: 
Merge, & Quick sort may be fast. But they are hard to understand. Well for me any way. Bubble Sort and the minor sorts seem to make sence. Rolling Eyes
Author:  wtd [ Tue Jan 03, 2006 11:37 pm ]
Post subject: 
Geminias wrote:
the reason i asked about the underscore was because i thought iterator was a member function of istream. i didnt realize istream_iterator was a class. I pretty much understand now. TY Wink


http://www.sgi.com/tech/stl/
Author:  md [ Wed Jan 04, 2006 12:17 am ]
Post subject: 
thuvs wrote:
Merge, & Quick sort may be fast. But they are hard to understand. Well for me any way. Bubble Sort and the minor sorts seem to make sence. Rolling Eyes

Bubble sort is a great thing to start off with precisely because it _is_ easy to understand. But once you get the hang of it learning how quick sort and merge sort work is a good idea.
Author:  DIIST [ Wed Jan 04, 2006 11:29 am ]
Post subject: 
Cornflake wrote:

Bubble sort is a great thing to start off with precisely because it _is_ easy to understand. But once you get the hang of it learning how quick sort and merge sort work is a good idea.


I wonder if there is like a tutorial that explains the different sorting algorithms. I personally learned bubble sort and the minor sorts form google sites. Its only shell sort and up, that i dont get. Confused

Shell sort uses 2d arrays though so i guess you have to go 3d, if you are dealing with sorting strings. Question
Author:  Geminias [ Wed Jan 04, 2006 6:36 pm ]
Post subject: 
you wouldn't "have" to go 3d arrays. its absolutely no different except in terms of organization. so if you thought it would be easier you could do a 1d array Laughing

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy