How do I do MergeSort versus QuickSort instead?

dxfist · 03-05-2008, 04:05 PM

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.

**laserlight** · 03-05-2008, 09:51 PM

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.

iMalc · 03-06-2008, 12:09 AM

Quote:

Originally Posted by dxfist

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.

dxfist · 03-06-2008, 08:53 AM

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.

matsp · 03-06-2008, 08:58 AM

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

dxfist · 03-06-2008, 10:27 AM

I'm still stuck and confused, and the "Ask an Expert" function isn't working.

matsp · 03-06-2008, 10:33 AM

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

dxfist · 03-06-2008, 10:59 AM

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.

anon · 03-06-2008, 11:34 AM

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.

dxfist · 03-06-2008, 12:12 PM

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.

03-05-2008, 09:51 PM	#2
laserlight C++ Witch 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

03-06-2008, 08:58 AM	#5
matsp 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

03-06-2008, 10:27 AM	#6
dxfist 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

03-06-2008, 12:12 PM	#10
dxfist 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

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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