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
Attachments
/*

    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

>I want middle [Iterator type ] to be static
And what are you expecting this kind of optimization to buy you?

>I want middle [Iterator type ] to be static
And what are you expecting this kind of optimization to buy you?

Imagine I'm sorting a very large array, the idea is to minimize the number of variables declared, and kept in memory, the branching factor of merge sort is two that's okay, and acceptable, but still any other sort of optimization is welcome.

AViD

This article has been dead for over six months. Start a new discussion instead.