Re: Efficient sorting
"C++ Newbie" <newbie.cpp@googlemail.com> 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 reporting 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! ]