C Board  

Go Back   C Board > General Programming Boards > C++ Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 03-05-2008, 04:05 PM   #1
Registered User
 
Join Date: Jan 2008
Posts: 15
How do I do MergeSort versus QuickSort instead?

Hey all,
I have a program here that does MergeSort versus ExchangeSort, but what I want to know is how do you change the program to MergeSort versus QuickSort instead?

Code:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>		// Needed for rand() function
#include <ctime>		// needed for time() function
using namespace std;

ofstream fout("Mergesort_versus_ExchangeSort_output.txt");

//***********************************************************************************
void Merge(int h, int m, const int U[], const int V[], int S[]) 
{
     int j = 0;
     int k = 0;
 for (int i = h; i < m; i++)
 {
     if (U[j] < V[k]) {
     S[i] = U[j];
     j++;
     }
 else
 {
     S[i] = V[k];
     k++;
   }
 }
}

//***********************************************************************************
void Swap(int & a, int & b)
{
	int temp;
    temp = a;
    a = b;
    b = temp;


}
//***********************************************************************************
void ExchangeSort(int n, int S[])
{

int i, j;
for(i = 1; i <= 1; i++)
for(j = i + 1; j<= n; j++) {
      
if (S[j] < S[i]) {
Swap(S[i], S[j]);
}
 }

}
//***********************************************************************************
void MergeSort(long n, int S[])
{

if(n > 1)
{
     int U[n/2];
     int V[n/2];
     MergeSort(n/2,U);
     MergeSort(n/2,V);
      
}
	
}
//***********************************************************************************
void StringOutput(char * s)
{
	cout << s;
	fout << s;
}
//***********************************************************************************
void OutputArray(long n, int S[])
{
	long i;
	for (i = 1; i <= n; i++)
	{
		cout << S[i] << "  ";
		fout << S[i] << "  ";
	}
	cout << endl << endl;
	fout << endl << endl;
}
//***********************************************************************************
int main()
{
	cout << fixed << setprecision(3);	
	fout << fixed << setprecision(3);	

	StringOutput("------------------------------------------------------------\n");
	StringOutput("MergeSort vs. ExchangeSort.\n");
	StringOutput("------------------------------------------------------------\n\n\n");

	long n,				// size of the array
		 i,				// loop counter
 		 initialSize,
		 lastSize,
		 increment;

	int	upperLimit,		// values in array will be from 1 to upperLimit
		*S_0,			// S_0 stores the unsorted array
		*S_1,			// S_1 array will be MergeSorted
		*S_2;			// S_2 array will be ExchangeSorted

	clock_t  startExchangeSort, endExchangeSort, startMergeSort, endMergeSort; 

	srand(time(NULL)*1000);  // Seed the random number generator

	//************  PART 1  **********************************************************************
	StringOutput("--- Part 1 --------------------------------------------\n");
	StringOutput("First we will test if MergeSort and ExchangeSort work:\n\n\n\n");
	
	StringOutput("Enter the size of the array, or 0 to move on:  ");
	cin >> n;
	fout << n << endl;

	while (n > 0)
	{
		StringOutput("Enter the upper limit of array elements:  ");
		cin >> upperLimit;
		fout << upperLimit << endl;

		S_0 = new int[n+1];
		S_1 = new int[n+1];
		S_2 = new int[n+1];

		for (i = 1; i <= n; i++)
			S_0[i] = S_1[i] = S_2[i] =  1 + rand() % upperLimit;

		MergeSort(n, S_1);
		ExchangeSort(n, S_2);
			
		StringOutput("\nUnsorted, the array is: \n\n");
		OutputArray(n, S_0);

		StringOutput("MergeSort results in: \n\n");
		OutputArray(n, S_1);

		StringOutput("ExchangeSort results in: \n\n");
		OutputArray(n, S_2);

		delete S_0;
		delete S_1;
		delete S_2;

		StringOutput("------------------------------------------------------------\n");
		
		StringOutput("\nEnter the size of the array, or 0 to move on:  ");
		cin >> n;
		fout << n << endl;
	}


	//************  PART 2  **********************************************************************
	StringOutput("\nMoving on...\n\n\n\n\n");
	StringOutput("--- Part 2 -----------------------------------------------------------------\n");
	StringOutput("Now we will time MergeSort vs. ExchangeSort.\n\n\n");

	StringOutput("Enter the upper limit of array elements (to be used for all tests):  ");
	cin >> upperLimit;
	fout << upperLimit << endl;

	StringOutput("\n\nEnter the initial size of the list, or 0 to quit:  ");
	cin >> initialSize;
	fout << initialSize << endl;

	while (initialSize > 0)
	{
		StringOutput("Enter the lastSize of the list:  ");
		cin >> lastSize;
		fout << lastSize << endl;
		StringOutput("Enter the increment:  ");
		cin >> increment;
		fout << increment << endl;

		StringOutput("\n\n    Size      MergeSort         ExchangeSort\n");
		StringOutput("---------------------------------------------------------------\n\n");

		for (n = initialSize; n <= lastSize; n = n + increment)
		{
			S_1 = new int[n+1];
			S_2 = new int[n+1];

			for (i = 1; i <= n; i++)
				S_1[i] = S_2[i] =  1 + rand() % upperLimit;

			cout << setw(8) << n;
			fout << setw(8) << n;

			startMergeSort = clock();
			MergeSort(n, S_1);
			endMergeSort = clock();

			cout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";
			fout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";

			startExchangeSort = clock();
			ExchangeSort(n, S_2);
			endExchangeSort = clock();

			cout << setw(13) << double((endExchangeSort - startExchangeSort))/CLK_TCK << " sec.\n";
			fout << setw(13) << double((endExchangeSort - startExchangeSort))/CLK_TCK << " sec.\n";

			delete S_1;
			delete S_2;
		}

		StringOutput("------------------------------------------------------------------------------\n\n");
		StringOutput("\n\nEnter the initial size of the list, or 0 to move on:  ");
		cin >> initialSize;
		fout << initialSize << endl;
	}  

	
	//************  PART 3  **********************************************************************
	StringOutput("\nMoving on...\n\n\n\n\n");
	StringOutput("--- Part 3 -----------------------------------------------------------------\n");
	StringOutput("Now we will just time MergeSort by itself on very large list sizes.\n\n\n\n");
	
	StringOutput("Enter the initial size of the list, or 0 to quit:  ");
	cin >> initialSize;
	fout << initialSize << endl;

	while (initialSize > 0)
	{
		StringOutput("Enter the lastSize of the list:  ");
		cin >> lastSize;
		fout << lastSize << endl;
		StringOutput("Enter the increment:  ");
		cin >> increment;
		fout << increment << endl;

		StringOutput("\n\n      Size        MergeSort \n");
		StringOutput("------------------------------------------------------------------------------\n\n");

		for (n = initialSize; n <= lastSize; n = n + increment)
		{
			S_1 = new int[n+1];

			for (i = 1; i <= n; i++)
				S_1[i] =  1 + rand() % upperLimit;

			cout << setw(10) << n;
			fout << setw(10) << n;

			startMergeSort = clock();
			MergeSort(n, S_1);
			endMergeSort = clock();

			cout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";
			fout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";

			delete S_1;
		}

		StringOutput("------------------------------------------------------------------------------\n\n");
		StringOutput("\n\nEnter the initial size of the list, or 0 to quit:  ");
		cin >> initialSize;
		fout << initialSize << endl;
	}  

	StringOutput("\nBye!\n\n");
}
Any help is appreciated...thanks for your time.
dxfist is offline   Reply With Quote
Old 03-05-2008, 09:51 PM   #2
C++ Witch
 
laserlight's Avatar
 
Join Date: Oct 2003
Location: Singapore
Posts: 11,338
Implement quicksort, then substitute the function for the exchange sort function.

Note that if this were not an exercise, you would just use std::sort() instead of quicksort and std::stable_sort() if you want a stable sort like mergesort.
__________________
C + C++ Compiler: MinGW port of GCC
Build + Version Control System: SCons + Bazaar

Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
laserlight is offline   Reply With Quote
Old 03-06-2008, 12:09 AM   #3
Algorithm Dissector
 
iMalc's Avatar
 
Join Date: Dec 2005
Location: New Zealand
Posts: 2,733
Quote:
Originally Posted by dxfist View Post
Hey all,
I have a program here that does MergeSort versus ExchangeSort, but what I want to know is how do you change the program to MergeSort versus QuickSort instead?
I can't understand how it could be possible that you wrote the posted code and yet don't know the answer.
__________________
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline   Reply With Quote
Old 03-06-2008, 08:53 AM   #4
Registered User
 
Join Date: Jan 2008
Posts: 15
I know, but I don't program in C++ that much.

I tried to redo the code and replace ExchangeSort with QuickSort:

Code:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>		// Needed for rand() function
#include <ctime>		// needed for time() function
using namespace std;

ofstream fout("MergeSort_versus_Quicksort_output.txt");

//***********************************************************************************
void Merge(int h, int m, const int U[], const int V[], int S[]) 
{
     int j = 0;
     int k = 0;
 for (int i = h; i < m; i++)
 {
     if (U[j] < V[k]) {
     S[i] = U[j];
     j++;
     }
 else
 {
     S[i] = V[k];
     k++;
   }
 }
}

//***********************************************************************************
void Swap(int & a, int & b)
{
	int temp;
    temp = a;
    a = b;
    b = temp;


}
//***********************************************************************************
void Partition(int low, int high, int S[])
{

int i, j;
int pivotpoint, pivotitem;

pivotitem = S[low];
j = low;
for(i = low + 1; i <= high; i++) 
    if (S[i] < pivotitem) {
    j++;
    Swap(S[i], S[j]);
    }
pivotpoint = j;
Swap(S[low], S[pivotpoint]);

}
//***********************************************************************************
void QuickSort(int low, int high)
{

int pivotpoint;

if(high > low) {
        Partition(low,high,pivotpoint);
        QuickSort(low, pivotpoint - 1);
        QuickSort(pivotpoint + 1, high);

}
 }

//***********************************************************************************
void MergeSort(long n, int S[])
{

if(n > 1)
{
     int U[n/2];
     int V[n/2];
     MergeSort(n/2,U);
     MergeSort(n/2,V);
      
}
	
}
//***********************************************************************************
void StringOutput(char * s)
{
	cout << s;
	fout << s;
}
//***********************************************************************************
void OutputArray(long n, int S[])
{
	long i;
	for (i = 1; i <= n; i++)
	{
		cout << S[i] << "  ";
		fout << S[i] << "  ";
	}
	cout << endl << endl;
	fout << endl << endl;
}
//***********************************************************************************
int main()
{
	cout << fixed << setprecision(3);	
	fout << fixed << setprecision(3);	

	StringOutput("------------------------------------------------------------\n");
	StringOutput("MergeSort vs. QuickSort.\n");
	StringOutput("------------------------------------------------------------\n\n\n");

	long n,				// size of the array
		 i,				// loop counter
 		 initialSize,
		 lastSize,
		 increment;

	int	upperLimit,		// values in array will be from 1 to upperLimit
		*S_0,			// S_0 stores the unsorted array
		*S_1,			// S_1 array will be MergeSorted
		*S_2;			// S_2 array will be QuickSorted

	clock_t  startQuickSort, endQuickSort, startMergeSort, endMergeSort; 

	srand(time(NULL)*1000);  // Seed the random number generator

	//************  PART 1  **********************************************************************
	StringOutput("--- Part 1 --------------------------------------------\n");
	StringOutput("First we will test if MergeSort and QuickSort work:\n\n\n\n");
	
	StringOutput("Enter the size of the array, or 0 to move on:  ");
	cin >> n;
	fout << n << endl;

	while (n > 0)
	{
		StringOutput("Enter the upper limit of array elements:  ");
		cin >> upperLimit;
		fout << upperLimit << endl;

		S_0 = new int[n+1];
		S_1 = new int[n+1];
		S_2 = new int[n+1];

		for (i = 1; i <= n; i++)
			S_0[i] = S_1[i] = S_2[i] =  1 + rand() % upperLimit;

		MergeSort(n, S_1);
		QuickSort(low, high, S_2);
			
		StringOutput("\nUnsorted, the array is: \n\n");
		OutputArray(n, S_0);

		StringOutput("MergeSort results in: \n\n");
		OutputArray(n, S_1);

		StringOutput("QuickSort results in: \n\n");
		OutputArray(n, S_2);

		delete S_0;
		delete S_1;
		delete S_2;

		StringOutput("------------------------------------------------------------\n");
		
		StringOutput("\nEnter the size of the array, or 0 to move on:  ");
		cin >> n;
		fout << n << endl;
	}


	//************  PART 2  **********************************************************************
	StringOutput("\nMoving on...\n\n\n\n\n");
	StringOutput("--- Part 2 -----------------------------------------------------------------\n");
	StringOutput("Now we will time MergeSort vs. QuickSort.\n\n\n");

	StringOutput("Enter the upper limit of array elements (to be used for all tests):  ");
	cin >> upperLimit;
	fout << upperLimit << endl;

	StringOutput("\n\nEnter the initial size of the list, or 0 to quit:  ");
	cin >> initialSize;
	fout << initialSize << endl;

	while (initialSize > 0)
	{
		StringOutput("Enter the lastSize of the list:  ");
		cin >> lastSize;
		fout << lastSize << endl;
		StringOutput("Enter the increment:  ");
		cin >> increment;
		fout << increment << endl;

		StringOutput("\n\n    Size      MergeSort         QuickSort\n");
		StringOutput("---------------------------------------------------------------\n\n");

		for (n = initialSize; n <= lastSize; n = n + increment)
		{
			S_1 = new int[n+1];
			S_2 = new int[n+1];

			for (i = 1; i <= n; i++)
				S_1[i] = S_2[i] =  1 + rand() % upperLimit;

			cout << setw(8) << n;
			fout << setw(8) << n;

			startMergeSort = clock();
			MergeSort(n, S_1);
			endMergeSort = clock();

			cout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";
			fout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";

			startQuickSort = clock();
			QuickSort(low, high, S_2);
			endQuickSort = clock();

			cout << setw(13) << double((endQuickSort - startQuickSort))/CLK_TCK << " sec.\n";
			fout << setw(13) << double((endQuickSort - startQuickSort))/CLK_TCK << " sec.\n";

			delete S_1;
			delete S_2;
		}

		StringOutput("------------------------------------------------------------------------------\n\n");
		StringOutput("\n\nEnter the initial size of the list, or 0 to move on:  ");
		cin >> initialSize;
		fout << initialSize << endl;
	}  

	
	//************  PART 3  **********************************************************************
	StringOutput("\nMoving on...\n\n\n\n\n");
	StringOutput("--- Part 3 -----------------------------------------------------------------\n");
	StringOutput("Now we will just time MergeSort by itself on very large list sizes.\n\n\n\n");
	
	StringOutput("Enter the initial size of the list, or 0 to quit:  ");
	cin >> initialSize;
	fout << initialSize << endl;

	while (initialSize > 0)
	{
		StringOutput("Enter the lastSize of the list:  ");
		cin >> lastSize;
		fout << lastSize << endl;
		StringOutput("Enter the increment:  ");
		cin >> increment;
		fout << increment << endl;

		StringOutput("\n\n      Size        MergeSort \n");
		StringOutput("------------------------------------------------------------------------------\n\n");

		for (n = initialSize; n <= lastSize; n = n + increment)
		{
			S_1 = new int[n+1];

			for (i = 1; i <= n; i++)
				S_1[i] =  1 + rand() % upperLimit;

			cout << setw(10) << n;
			fout << setw(10) << n;

			startMergeSort = clock();
			MergeSort(n, S_1);
			endMergeSort = clock();

			cout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";
			fout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";

			delete S_1;
		}

		StringOutput("------------------------------------------------------------------------------\n\n");
		StringOutput("\n\nEnter the initial size of the list, or 0 to quit:  ");
		cin >> initialSize;
		fout << initialSize << endl;
	}  

	StringOutput("\nBye!\n\n");
}
I get the following errors:
Line 67: invalid conversion from int to int
intializing argument 3 of void Partition(int, int, int)

Line 153: low undeclared (first use this function)
high undeclared (first use this function)

How do I fix these errors? Thanks again for your help in advance.
dxfist is offline   Reply With Quote
Old 03-06-2008, 08:58 AM   #5
Kernel hacker
 
Join Date: Jul 2007
Location: Farncombe, Surrey, England
Posts: 15,686
First of all, it looks like you are not defining QuickSort with the right number of arguemnts. Second, Partition() needs to have an array passed as the third argument, you are passing the "MidPoint".

And you call
QuickSort(low, high, S_2);
But low and high aren't declared in that function.

--
Mats
__________________
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
matsp is offline   Reply With Quote
Old 03-06-2008, 10:27 AM   #6
Registered User
 
Join Date: Jan 2008
Posts: 15
I'm still stuck and confused, and the "Ask an Expert" function isn't working.
dxfist is offline   Reply With Quote
Old 03-06-2008, 10:33 AM   #7
Kernel hacker
 
Join Date: Jul 2007
Location: Farncombe, Surrey, England
Posts: 15,686
Code:
void Partition(int low, int high, int S[])
{

int i, j;
int pivotpoint, pivotitem;

pivotitem = S[low];
j = low;
for(i = low + 1; i <= high; i++) 
    if (S[i] < pivotitem) {
    j++;
    Swap(S[i], S[j]);
    }
pivotpoint = j;
Swap(S[low], S[pivotpoint]);

}
//***********************************************************************************
void QuickSort(int low, int high)
{

int pivotpoint;

if(high > low) {
        Partition(low,high,pivotpoint);
        QuickSort(low, pivotpoint - 1);
        QuickSort(pivotpoint + 1, high);

}
 }
Pivotpoint is NOT the right argument for Partition.


Code:
		MergeSort(n, S_1);
		QuickSort(low, high, S_2);
			
		StringOutput("\nUnsorted, the array is: \n\n");
		OutputArray(n, S_0);
low and high are not present in the function. What do you think you need to pass to start a sort off?

S_2 is passed to the function, but the function only takes 2 arguments.


--
Mats
__________________
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
matsp is offline   Reply With Quote
Old 03-06-2008, 10:59 AM   #8
Registered User
 
Join Date: Jan 2008
Posts: 15
Code:
//***********************************************************************************
void Partition(int low, int high, int S[])
{

int i, j;

int pivotpoint, pivotitem;

pivotitem = S[low];
j = low;
for(i = low + 1; i <= high; i++) 
    if (S[i] < pivotitem) {
    j++;
    Swap(S[i], S[j]);
    }
pivotpoint = j;
Swap(S[low], S[pivotpoint]);

}
//***********************************************************************************
void QuickSort(int low, int high)
{

int pivotpoint;

if(high > low) {
        Partition(low,high);
        QuickSort(low, pivotpoint - 1);
        QuickSort(pivotpoint + 1, high);

}
 }
Ok, I get an error that says too few arguments to function void Partition(int, int int) and at line 68 for Partition(low,high); "at this point in file".

And I still don't get what you're saying about high and low.
dxfist is offline   Reply With Quote
Old 03-06-2008, 11:34 AM   #9
The larch
 
Join Date: May 2006
Posts: 3,222
The function Partition takes three arguments, but you pass only two.

In addition it doesn't look like anything a Partition should look like. This ExchangeSort is a completely different kind - O(n^2) - of a sort than QuickSort - O(n log 2), and there is no way you can "modify" it into a quicksort.

Perhaps you should start by reading up about Quicksort, for example in Wikipedia which might have the pseudocode or even real code if you are lucky.
__________________
I might be wrong.

Quote:
Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
Quoted more than 1000 times (I hope).
anon is offline   Reply With Quote
Old 03-06-2008, 12:12 PM   #10
Registered User
 
Join Date: Jan 2008
Posts: 15
The pseudocode is exactly the same as the one I just put, so that doesn't help. I know i'm coming off like a newb, but I have no idea what i'm doing at this point and if I can't "modify" the ExchangeSort into QuickSort, then i'm in trouble.
dxfist is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
How to sort a simple linked list using swap-sort method JOCAAN C Programming 24 08-07-2009 11:48 AM
Scalability problems with Quicksort hbejkosa C++ Programming 3 12-26-2008 11:26 PM
Natural Mergesort wuzzo87 C Programming 31 04-14-2007 09:41 PM
Using quicksort and radix sort for an anagram program RazielX C Programming 2 05-03-2004 09:33 AM
Quicksort Nutshell C Programming 1 01-15-2002 09:42 AM


All times are GMT -6. The time now is 09:21 AM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22