Okay, guys, after running a thread bout tht nth_element problem [ which is still not solved ] I again have a problem.
The code I give below [ I have also attached the file ], is simply a MergeSort procedure. It works wonderfully well. I have enabled validation of it in the code itself.
But the problem is that, I want somehow the line 49 and 50 to be optimized. I want middle [Iterator type ] to be static, so that there is only one copy of it in the memory, can anyone suggest anything. I dn't think putting it static would work, cause their are two calls to merge_sort in between which value of the single static variable will get lost.
If anyone can come up with any other optimization, I will appreciate it.
AViD
/*
Title : MergeSort Using STL Algorithms to merge, and validate
Created On : 3rd April, 2008
Last Modified On : 3rd April, 2008
Authored By : Abhishek Vaid (a.vaid@iiitm.ac.in, vaid.abhishek@hotmail.com)
Platform : Standard C++
Input file : No Stanard Input, Randomized Input
Description : This program illustrates the use of standard STL Algorithms and how they can be used to solve various
steps used in the standard MergeSort Algorithm given in CLR.
*/
// Headers to be included, NOT ALL ARE USED
#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#include <string>
#include <iterator>
#include <cmath>
using namespace std;
// MACROS Defined
#define NUMBEROFCASES 10000 // Defines the number of cases to be solved
#define INPUTSIZE 50 // Defines the size of the array to be sorted
#define MAXNUMBER 999 // Defines the MAXNUMBER to be held in the array
// Typedef's
typedef vector<int> VInt;
typedef VInt::iterator VIntItor;
/* *-- MergeSort Algorithm --*
Synopsis: This Algorithm Strictly Sorts the range of arr given from start to end. The sorting done is stable
and algorithm uses linear algorithm inplace_sort to sort the output. The standard logic of the algorithm
is taken from CLR.
*/
void Merge_Sort ( VInt &arr, VIntItor start, VIntItor end ) {
if (start < end ) {
VIntItor middle;
middle = start + (int)floor ( ( distance(start,end) ) / 2 ) ;
Merge_Sort (arr, start, middle);
Merge_Sort (arr, middle+1, end);
inplace_merge (start, (middle+1), (end+1));
}
}
/* *-- MyIntegerRand : Function Object --*
Synopsis: This is the MyIntegerRand Function Object, which uses the underneath rand function to obtained a random
value (Integer Type) between 1 - LIMIT (LIMIT is passed as a constructor argument). The function also
seeds srand() function with a random seed at the start.
*/
class MyIntegerRand
{
public:
MyIntegerRand ( int limit ) {
this->limit = limit;
time_t seed; // Generating a random Seed at start up
time (&seed);
srand ((unsigned long) seed );
}
int operator() () {
return ( (rand() % limit) + 1 );
}
private:
int limit;
};
int main (){ // START OF MAIN
VInt arr (INPUTSIZE); // An Array (vector ) of INPUTSIZE Integer Elements
MyIntegerRand myIntegerRand (MAXNUMBER); // A Function Object defined with limit of MAXNUMBER
ofstream out; // AN output file to flush all the output
out.open ("output.txt");
for ( long i = 1 ; i <= NUMBEROFCASES ; i++ ) { // SET NUMBEROFCASES AT THE START OF THE PROGRAM
generate ( arr.begin(), arr.end(), myIntegerRand ); // fills the array with random values from 1 - MAXNUMBER
Merge_Sort ( arr, arr.begin(), (arr.end() - 1) );
assert ( adjacent_find ( arr.begin(), arr.end(), greater <int> () ) == arr.end() ); // It validates the sorted array
out <<"\n\nTest Case " << i << endl;
copy ( arr.begin(), arr.end(), ostream_iterator <int> (out, ", ") ); // flushes the array to output file
}
out.close();
cout << "\n All the output is flushed to the file \"output.txt\" in the directory of the program ";
system("pause");
} // END OF MAIN