macOS Quick C++ question.

[Sirena400]

Hey all, I'm in the current process of writing a program that can sort words in alphabetical order. Right now I'm just testing it with a small list to see if it works before I use it on another project. I wrote the test in notebook and the list is: sat, cat, rat each on it's own line. What my program should do is look at each word and sort them in alphabetical order so it should read: cat, sat, rat. But what happens when I run the program is it only shows the last word rat, I think I messed up with the logic somewhere but I don't know where. Anyone have any suggestions as to a way to make it so the whole list shows up?

#include <iostream.h>
#include "apstring.h"
#include "apvector.h"
#include <fstream.h>

int main()
{
ifstream inwords;
inwords.open("test.txt");
apvector<apstring>word(100);
int x;
apstring temp="";
bool run=false;
for(x=0; x<word.length()-2;x++)
{
inwords>>word[x];
for(int y=x+1; y<word.length()-1;y++)
{
if(word[x]>word[y])
{
run=true;
temp=word[x];
word[x]=word[y];
word[y]=temp;
run=false;
}
}
}

cout<<temp<<endl;

return 0;
}

Thanks in advance

 

[csubear]

Is this for a class or for your self?

I would do this.

#include <vector>
#include <string>
#include <algorithms>
#include <iostream>


int main(void)
{
vector<std::string> listOwords;
listOwords.push_back("sat");
listOwords.push_back("rat");
listOwords.push_back("cat");

sort(listOwords.begin(),listOwords.end());

for(vector<std::string>::iterator currentWord = listOwords.begin;
currentWord != listOwords.end();currentWord++)
{
std::cout << *currentWord << std::endl;
}

}

something like this should do it. check out http://www.sgi.com/tech/stl/ for more info on the standard template libray. its a great tool

 

[plinden]

I agree with csubear. Unless you're forced to write your own code for a class, using the STL sort is the easiest. There are faster string sorting algorithms out there, but the STL sort should be fine ... unless, STL sort is case sensitive, so sat fat Rat would be sorted as Rat fat sat. Is that what you want?

 

[csubear]

The stl sort uses what every string uses for < or >... it maybe case sensitive. And you can overridde the sort comparsion if you want to aswell.

 

[csubear]

if your teacher is making you write you own sort take a look at this

http://linux.wku.edu/~lamonml/algor/sort/sort.html


its a good ref for all the well know sort alogrithm. It looks like you where trying to do a bubble sort.

 

[AdamR01]

I could never understand why on earth they would make something as dumb as the AP classes. I mean they are only good for taking the AP test anyways and now the AP test is over Java if i am remembering right. If you tell me you are using the book C++ for You++ I will tell you to forget everything that book teaches you before you start college. That was the absolute worst book I have ever had for a class. If you are in College, then your professor should not be making you use the AP classes.

 

[MarkCollette]

It looks like you're trying to do an insertion sort.

You're adding entries one at a time, into index x.

There are no entries after x, but you're looking for a new slot at location y, which starts at x+1.

Instead, you should be looking between 0 and x-1 inclusive. As well, don't swap entries at locations x and y. Remove it from x and insert it at y.

Also, you have only one cout, at the end of the program, showing temp, which contains the last swapped entry. You need a separate loop to iterate over the sorted array, using cout on each entry.

 

[Sirena400]

Sorry, I should've been more specific. I'm doing this for a highschool class, yes it is an insertion sort, and our teacher did specifically want us to learn this sort and to get used to the for loop within in a for loop so I'd like to use the STL sort but I can't, sorry. MarkCollette: I tried to get it so it looked between 0 and x-1 but that produced an illegal index error. I don't think that's the wrong error, I moved the cout<<temp<<endl; into the the if statement, under the statement word[y]=temp; and that worked to show the whole list of cat, sat, rat but unfortunately it wasn't in the right order and came out sat cat rat.

 

[MarkCollette]

Sorry, I should've been more specific. I'm doing this for a highschool class, yes it is an insertion sort, and our teacher did specifically want us to learn this sort and to get used to the for loop within in a for loop so I'd like to use the STL sort but I can't, sorry. MarkCollette: I tried to get it so it looked between 0 and x-1 but that produced an illegal index error. I don't think that's the wrong error, I moved the cout<<temp<<endl; into the the if statement, under the statement word[y]=temp; and that worked to show the whole list of cat, sat, rat but unfortunately it wasn't in the right order and came out sat cat rat.

It sounds like you're a little new to programming, algorithms, and C++, so that if something doesn't work you're unsure why. In that situation, I recommend breaking things into smaller pieces.

For starters, try making a pseudocode representation of your algorithm, glossing over any C++ specific issues.

Eg:

Vector fileContents
Vector sorted

Read file into fileContents
Foreach entry in fileContents

int index = findInsertionPoint( sorted, entry )
sorted.insert( entry, index )
​

Foreach entry in sorted

print entry​

Then refine the missing parts of pseudocode, like method findInsertionPoint(). All of that is on paper, or a text editor, but is not C++ code. Make sure you understand and believe in every line of your pseudocode before you even try to put it into C++.

One thing you'll see from my example, was that using a separate Vector for the file list than for the sorted list, can simplify things. I don't know if your assignment specifies sorting a single Vector in place, or if it allows the easier approach of using two Vectors.

Finally, if you get errors, like the illegal index error, try to think how your algorithm could be correct, but maybe your C++ implementation has a little error. For example, there might be a base case where, when sorting the first entry, at index = 0. that (index - 1) is invalid, so it needs special handling.

 

[Sirena400]

Yeah I'm still a newbie to C++ ^^; Thanks MarkCollette for the help, going through it like that did help and it is now sorting correctly, but the cout statement that gets printed out onto the screen keeps repeating itself over and over again. I think to fix it I need to put the cout statement in its own for loop and in that loop set the size of the cout statement from 0 to the amount of words in the list, but I don't know how I should do that, any suggestions? (I'm still using the list cat sat rat by the way)

#include <iostream.h>
#include "apstring.h"
#include "apvector.h"
#include <fstream.h>

int main()
{
ifstream inwords;
inwords.open("test.txt");
apvector<apstring>word(100);
apstring temp="";
int y=0;
while(inwords>>word[y])
y++;
for(int x=0; x<word.length()-2;x++)
{
for(int y=x+1; y<word.length()-1;y++)
{
if(word[x]>word[y])
{
temp=word[x];
word[x]=word[y];
word[y]=temp;
cout<<temp<<endl;
}
}
}
return 0;
}

 

[MarkCollette]

One thing you should be aware of, is that there are many different types of sorts. What your code is approaching is a bubble sort, but your assignment requires an insertion sort.

Many sorting anglorithms take a given list of items, and then sort that list.
The idea behind insertion sort is that you have a blank slate to put items into, so none of the other unsorted items are in the way. As you insert items, you put them in at the right place. So this list is always sorted, at every step. Once all items have been inserted, you're done.

In my previous example I showed reading into one list, and then insertion sorting into another list. One doesn't really need two lists, but can simply insert straight away, while reading from the file.

ifstream inwords;
inwords.open("test.txt");
apvector<apstring>word(100);
apstring temp="";
while(inwords>>temp) {
	// I have no idea if the while(inwords>>temp) above
	//   will break on end of file, or if you have to
	//   test temp to see if it's empty (temp.length()==0)
	//   and then break from the while loop

	// temp contains the current string
	// must find where to put it in word
	// valid indexes are from 0 to word.length() inclusive
	int i = 0;
	while( i < word.length() && temp > word[i] )
		i++;
	// Look at the main cases to make sure i is our insertion index
	//  - word was empty, should insert at 0 : i=0 ==> good
	//  - word had one entry, temp should go first : i=0 < 1 but temp<word[0] so break with i=0 ==> good
	//  - word had one entry, temp should go second : i=0 < 1 && temp>word[0] so i++ with i=1 ==> good
	
	// Now, ideally class apvector has an insert or add method,
	//   which will push everything down one, and put the
	//   new entry into the newly openned slot
	word.insert( i, temp );
	// But if it doesn't have an insert or add method that takes an index,
	//  then we can do it outself
	for(int y = word.length()-1; y >= i; y--)
		word[y+1] = word[y];
	word[i] = temp;
}

// Now we can print out the sorted list in word
for(int i = 0; i < word.length(); i++)
	cout << word[i] << endl;

 

[Sirena400]

Ah I get it now, thanks very much. I didn't realize how easy going through code could be, it always seemed hard to me. Thanks very much, MarkCollette, my program is working quite well and now I can add it to the program I wanted to. Thanks!

 

[MarkCollette]

Ah I get it now, thanks very much. I didn't realize how easy going through code could be, it always seemed hard to me. Thanks very much, MarkCollette, my program is working quite well and now I can add it to the program I wanted to. Thanks!

You're welcome. A lot of searching and sorting algorithms are conceptually simple, but the various implementations take a bit of effort.

The one I wrote in the previous post only used a linear search for the insertion point, but a more complex implementation might use a binary search for the insertion point, since the target vector's elements are ordered. In some contexts, I've taken the binary search, and prefixed it with a test against the last element, for when the input data is already mostly sorted., so it's most like to just add to the end.

My point is that, for productivity, you'll probably just use library sort routines, but it can help to understand the theory behind the algorithms, and to know that they can range from very simple to quite complex, depending on the application parameters.

 

[darkwing]

My point is that, for productivity, you'll probably just use library sort routines, but it can help to understand the theory behind the algorithms, and to know that they can range from very simple to quite complex, depending on the application parameters.

Mark is right. In my data structures class a couple quarters ago, I was always whining about not being able to use STL, but I am glad I had a chance to learn how a lot of these routines work.

Steven