"C++ Newbie" <newbie.cpp@[EMAIL PROTECTED]
> writes:
> Here's mine, with a random number generator at the end to make
> testfiles. How do I improve the efficiency of the sorting process?
> I've read about the various techniques but without statistical
> analysis it is not immediately clear which is best or if there is
> indeed a better way than the known best.
>
> Example: Number of operations with a random seed of 0 and a 100,000
> line file: 704982704 (assuming my definition of operations is the same
> as people who claim nlog(n) - n^2 operations)
>
> Thanks for any input.
>
> // This program sorts a vector of numbers in ascending order
> #include <fstream>
> #include <stdlib.h>
> #include <string>
> #include <iostream>
> #include <math.h>
>
> using namespace std;
>
> int main()
> {
> string line;
> int i=0, count = 0, temp_int2;
>
> fstream myfile("vector_in.txt");
> // Read in number of lines
> while (!myfile.eof())
> {
> getline(myfile,line);
> count++;
> }
>
> count = count - 1;
> myfile.clear(); // forget we hit the end of file
> myfile.seekg(0, ios::beg); // move to the start of the file
> cout << "Number of file lines = "<< count << "\n";
> int vector_in[count];
>
> // Read in data
> while (i < count)
> {
> getline(myfile,line);
> vector_in[i] = atoi(line.c_str());
> i++;
> }
First, this is an inefficient way of determining the number of lines,
and it may also be off by one (if the file doesn't end with an end of
line character (sequence)) or result in an eternal loop (if input
fails for a reason other than end-of-file).
Second, atoi() has no way of re****ting conversion failure; better use
the function std::strtol() or std::istream.
E.g.
std::vector<long> numbers;
while (getline(myfile,line))
{
std::istringstream is(line);
long number;
if (is >> number)
numbers.push_back(number);
else
; // deal with the erroneous line
}
or, somewhat more compact,
std::ifstream myfile("testfile");
std::istream_iterator<int> ii(myfile);
std::vector<int> numbers(ii,std::istream_iterator<int>());
if (myfile.eof())
; // entire file consumed without error; proceed
else
; // deal with error
> // Swapping sort
> int temp_int = 0, operations = 0;
>
> for (int j = 0; j < count; j++)
> {
> for (i = j+1; i < count; i++)
> {
> operations++;
> if (vector_in[i] < vector_in[j])
> {
> temp_int = vector_in[i];
> vector_in[i] = vector_in[j];
> vector_in[j] = temp_int;
> }
> }
> }
This algorithm is named "bubble sort". It's very easily implemented,
and very inefficient in general.
To find more efficient algorithms, get your hands on a good algorithms
book, or search the internet for e.g. "quicksort", "heap sort" or
"merge sort" (http://en.wikipedia.org/
has nice articles on all these
algorithms (including bubble sort)).
--
[ See http://www.gotw.ca/resources/clcm.htm
for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
