Thread: How do I do MergeSort versus QuickSort instead?

  1. #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.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #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.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    15
    I'm still stuck and confused, and the "Ask an Expert" function isn't working.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  8. #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.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    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).

  10. #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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  3. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  4. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 09:42 AM