Sorting strings by lengths

[ashworcp]

I'm trying to write a program that sorts strings by their lengths and use it on a text file I have to print out the ten shortest and ten longest lines.

I am not sure if I am on the right path and I am stuck. If someone could look over it and tell me where to go from here I would appreciate it! The biggest problem I am having is if I am suppose to read in the text file in the main and call my sort function and print out the lines there?? Is that right?

Here is the code:

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

using namespace std;

vector<string> lines;
vector<int> second;

void readLines(char *filename)
{
    string line;
    ifstream infile;
	infile.open(filename);
	if (!infile)
	{	       
       cerr << filename << " cannot open" << endl; 
          return; 
	}       
    getline(infile, line);
	while (!infile.eof())
	{
		lines.push_back(line);
		getline(infile, line);
	}  
	infile.close();
}


int binary_search(vector<int> &v, int size, int value)
{
    int from = 0;
	int to = size - 1;
	while (from <= to)
	{  
		int mid = (from + to) / 2;
		int len = lines[v[mid]].length();
		if (value == len) 
			return mid;
		if (value < len) to = mid - 1;
		else from = mid + 1;
	}	   
	return from;
}


void sort()
{
   int numberOfLines = lines.size();
   second.resize(numberOfLines); // second vector
   for (int i = 0; i < numberOfLines; i++)
   {   
		int len = lines[i].length();  // sort by line length
		int position = binary_search(second, i, len);
		for (int j = i - 1; j >= position; j--) 
			second[j + 1] = second[j]; // move elements
			second[position] = i; // insert new element
   }
}   

int main()
{

}

[hamsterman]

Are you able to write an algorithm which sorts a vector of integers? If yes, then just replace if(int1 < int2) with if(str1.length() < str2.length()) the rest does not change (except the obvious).
If no, either see bubble sort in wikipedia (there is some pseudocode) or just use std::sort (form algorithm header).

Your sorting algorithm is a bit strange. I see what your idea is, but it's hard to find the error.. Unless it is only that you missed {} around lines 57,58..

[ashworcp]

Are you saying that I need another function that sorts a vector of integers to replace my sort function?

[hamsterman]

No. I only mentioned integers because sorting them is more obvious. My point was that if you can write a sorting algorithm, you need only trivial changes to make it work with a different type and different method of comparison.

Did you try the adding the {}s ? I have a feeling this could be your whole problem..

[ashworcp]

I added the {}. Now am I suppose to read in the text file in the main and call my sort function and print out the lines there?

[hamsterman]

sure

[D80DSL3A]

Doesn't binary_search only work on an array that's already sorted?
You are using it within the sort() on line 55.

[Mathhead200]

I didn't look to see if this was the case but you can use a “binary style” search within some sorting algorithms. However, this is probably an error.

[hamsterman]

I don't think so. He only uses the binary_search on the sorted result.

[ashworcp]

I'm having trouble opening the text file... How can I do this?

[D80DSL3A]

I see. He only applies binary_search to the 1st i elements of second, which may be sorted at that point.
Other questions: Where are the elements of second initialized? Line 58 only?
Is he relying on a default value of 0 for the elements?
What is the role of second? Is it to hold indexes for ordering the lines by length.
ie: so that lines[ second[i] ] would be in order of increasing length?
I can't follow the logic so I shall duck out!

[hamsterman]

The code seems fine. Are you getting your "... cannot open" or some other error?

[ashworcp]

I am just not reading in anything... I don't know what to do in my main to read in the text file I have. I have nothing in main so far..

[hamsterman]

Try this in main:

readLines("whatever file you have");
for(unsigned i = 0; i < lines.size(); i++) std::cout << lines[i] << '\n';

What do you get?

[ashworcp]

It didn't print anything.

readLines("bible.txt");
for(int i = 0; i < lines.size(); i++)	
     cout << lines[i] << '\n';

[hamsterman]

Could it be that there is only one line in your text file? change line 22 to while(infile).
I really don't see anything else..

[ashworcp]

Same result it prints nothing

[hamsterman]

I compiled it and it worked fine both if file exists and if it doesn't.
Post your main(). Also, what is in bible.txt ?

[ashworcp]

int main()
{
	readLines("bible.txt");
	for(int i = 0; i < lines.size(); i++)	
		cout << lines[i] << '\n';
}

Bible.txt is part of the beginning of the Bible. I am using Microsoft Visual Studio and put Bible.txt under resource files. I don't need to read it in somehow before I compile .cpp file do I?

[hamsterman]

Umm, doesn't that exit immediately?