Sorting a linked-list will inherently be either O(N^2) or involve external random-access storage.
Vectors have random access storage. So do arrays. Sorting can be O(NlogN).
At 1000 elements you will begin to see a difference between O(N^2) and O(NlogN). At 1,000,000 elements you'll definitely notice the difference!
It is possible under very special situations to get O(N) sorting. (For example: Sorting a deck of playing cards. We can create a function(card) that maps each card to its sorted position.)
But in general, O(NlogN) is as good as it gets. So you might as well use STL's sort()!
Just add #include <algorithms>
All you'll need to add is an operator<(). Or a sort functor.
But one suggestion: For god's sake man, if you are going to sort on a date, either encode it as a long int representing seconds-since-epoch (mktime?), or at the very least use a "year/month/day-hour:minute:second.fraction" format. (And MAKE SURE everything is 2 (or 4) digits with leading zeros!) Comparing "6/22/2008-4:34" and "12/5/2007-14:54" will require parsing! Comparing "2008/06/22-04:34" with "2007/12/05-14:54" is much easier. (Though still much less efficient than comparing two integers!)
Rich wrote:
the other answers seem to get into syntax more which is what I'm really lacking.
Ok. With basic a "int" type we have:
#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << (i>0?", ":"") << DATA[i]; } cout << endl;
int
main()
{
// Creating and Sorting a stack-based array.
int d [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
PRINT(d,10);
sort( d, d+10 );
PRINT(d,10);
cout << endl;
// Creating a vector.
int eData [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
vector<int> e;
for(int i=0; i<10; i++ )
e.push_back( eData[i] );
// Sorting a vector.
PRINT(e,10);
sort(e.begin(), e.end());
PRINT(e,10);
}
With your own type we have:
class Data
{
public:
string m_PackLine;
string m_FileDateTime;
int m_NumberDownloads;
/* Lets simplify creating Data elements down below. */
Data( const string & thePackLine = "",
const string & theDateTime = "",
int theDownloads = 0 )
: m_PackLine ( thePackLine ),
m_FileDateTime ( theDateTime ),
m_NumberDownloads ( theDownloads )
{ }
/* Can't use constructor with arrays */
void set( const string & thePackLine,
const string & theDateTime,
int theDownloads = 0 )
{
m_PackLine = thePackLine;
m_FileDateTime = theDateTime;
m_NumberDownloads = theDownloads;
}
/* Lets simplify printing out down below. */
ostream & operator<<( ostream & theOstream ) const
{
theOstream << "PackLine=\"" << m_PackLine
<< "\" fileDateTime=\"" << m_FileDateTime
<< "\" downloads=" << m_NumberDownloads;
return theOstream;
}
/*
* This is IT! All you need to add to use sort()!
* Note: Sort is just on m_FileDateTime. Everything else is superfluous.
* Note: Assumes "YEAR/MONTH/DAY HOUR:MINUTE" format.
*/
bool operator< ( const Data & theOtherData ) const
{ return m_FileDateTime < theOtherData.m_FileDateTime; }
};
/* Rest of simplifying printing out down below. */
ostream & operator<<( ostream & theOstream, const Data & theData )
{ return theData.operator<<( theOstream ); }
/* Printing out data set. */
#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << "[" << i << "] " << DATA[i] << endl; } cout << endl;
int
main()
{
// Creating a stack-based array.
Data d [10];
d[0].set( "Line 1", "2008/01/01 04:34", 1 );
d[1].set( "Line 4", "2008/01/04 04:34", 4 );
d[2].set( "Line 0", "2008/01/00 04:34", 0 );
d[3].set( "Line 2", "2008/01/02 04:34", 2 );
d[4].set( "Line 8", "2008/01/08 04:34", 8 );
d[5].set( "Line 6", "2008/01/06 04:34", 6 );
d[6].set( "Line 3", "2008/01/03 04:34", 3 );
d[7].set( "Line 5", "2008/01/05 04:34", 5 );
d[8].set( "Line 9", "2008/01/09 04:34", 9 );
d[9].set( "Line 7", "2008/01/07 04:34", 7 );
// Sorting a stack-based array.
PRINT(d,10);
sort( d, d+10 );
PRINT(d,10);
cout << endl;
// Creating a vector.
vector<Data> e;
e.push_back( Data( "Line 1", "2008/01/01 04:34", 1 ) );
e.push_back( Data( "Line 4", "2008/01/04 04:34", 4 ) );
e.push_back( Data( "Line 0", "2008/01/00 04:34", 0 ) );
e.push_back( Data( "Line 2", "2008/01/02 04:34", 2 ) );
e.push_back( Data( "Line 8", "2008/01/08 04:34", 8 ) );
e.push_back( Data( "Line 6", "2008/01/06 04:34", 6 ) );
e.push_back( Data( "Line 3", "2008/01/03 04:34", 3 ) );
e.push_back( Data( "Line 5", "2008/01/05 04:34", 5 ) );
e.push_back( Data( "Line 9", "2008/01/09 04:34", 9 ) );
e.push_back( Data( "Line 7", "2008/01/07 04:34", 7 ) );
// Sorting a vector.
PRINT(e,10);
sort(e.begin(), e.end());
PRINT(e,10);
}