[RookieC++User]

Hello Everybody,

I am having some problems with my quick sort algorithm. When I comment out my last recursive call. It works fine, but when I uncomment my last recursive call. My variable iDown prints out a really large negative number. Which leads me to believe that it is going outside of my array. I have been trying to resolve this, but no luck yet. Any advice you can all offer would be greatly appreciated.

Thanks

#include <iostream>
#include <ctime>
using namespace std;

#include "Sort.h"

Sort::Sort(int numOfValues)
{
	mpSorted = NULL;
	mpRandom = NULL;

	fillRandom(10, 20);
}

Sort::~Sort()
{
	delete [] mpRandom;
}

int Sort::fillRandom(int nNums, int numRange)
{
	mpRandom = new int [nNums];
	mpSorted = new int [nNums];
	mSize = nNums;

	for(int i = 0; i < nNums; i++)
	{
		mpRandom[i] = rand() % numRange + 1;
	}
	return 0;
}

void Sort::bubbleSort()
{
	utilCopy();
	utilBubbleSort(mpSorted, mSize);
}

void Sort::selectionSort()
{
	utilCopy();
	utilSelectionSort(mpSorted, mSize);
}

void Sort::insertionSort()
{
	utilCopy();
	utilInsertionSort(mpSorted, mSize);
}

void Sort::quickSort()
{
	utilCopy();
	utilQuickSort(mpSorted, 0, mSize - 1);
}
void Sort::print()const
{
	utilPrint(mpSorted, mSize);
}

int Sort::utilCopy()
{
	for(int i = 0; i < mSize; i++)
	{
		mpSorted[i] = mpRandom[i];
	}
	return 0;
}
int Sort::utilPrint(int num[], int size)const
{
	for(int i = 0; i < size; i++)
		cout << num[i] << endl;
	cout << "Value of size " << size << endl;
	return 0;
}

int Sort::utilBubbleSort(int num[], int size)
{
	bool	swapMade	= true;
    int	    last	    = size - 1;
    int	    swap;

	long int startSeconds = time(NULL);
    // Perform the Bubble Sort algorithm
    for (int pass=0; pass<size && swapMade; pass++)
    {
        swapMade = false;
        for (int i=0; i<last; i++)
        {
            if (mpSorted[i] > mpSorted[i+1])
            {
                swap = mpSorted[i];
                mpSorted[i] = mpSorted[i+1];
                mpSorted[i+1] = swap;
                swapMade = true;
            }
        }
        last--;
    }
	long  int stopSeconds = time(NULL);

	cout << "It took " << stopSeconds - startSeconds << "to complete the sort" << endl;
	return 0;
}

int Sort::utilSelectionSort(int num[], int size)
{
    int		i;
    int		j;
    int		smallest;
    int		swap;

    // Perform the Selection Sort algorithm
    for (i=0; i<(size-1); i++)
    {
        smallest = i;
        for (j=i+1; j<size; j++)
            if (mpSorted[j] < mpSorted[smallest])
                smallest = j;

        swap = mpSorted[i];
        mpSorted[i] = mpSorted[smallest];
        mpSorted[smallest] = swap;
    }

	return 0;
}

int Sort::utilInsertionSort(int num[], int size)
{
	int	i;
    int	j;
    int	swap;

    // Perform the Insertion Sort algorithm
    for (i=1; i<size; i++)
    {
        swap = mpSorted[i];
        for (j=i; (j>0) && (swap < mpSorted[j-1]); j--)
            mpSorted[j] = mpSorted[j-1];
        mpSorted[j] = swap;
    }

	return 0;
}

int Sort::utilQuickSort(int num[], int start, int end)
{
	if(start == end)
		return 0;
	
	if(start >= end)
		return 0;
	
	int iUp = start;
	int iDown = end;
	int iPivot = num[(start + end) / 2];

	cout << "Value of iPivot " << iPivot << endl;//Debug statement
	for(;;)/>
	{
		while(num[iUp] <= iPivot)
			iUp++;

		while(num[iDown] >= iPivot)
			iDown--;

		if(iUp <= iDown)
		{
			int tmp = num[iUp];
			num[iUp] = num[iDown];
			num[iDown] = tmp;
		}
		else
			break;
		cout << "Value of iUp " << iUp << endl;//Debug statement
		cout << "Value of iDown " << iDown << endl;//Debug statement
	};
	cout << "Value of num[iUp] " << num[iUp] << endl;//Debug statement
	cout << "Value of num[iDown] " << num[iDown] << endl;//Debug statement
	
	utilQuickSort(num, start, iDown - 1);
	//utilQuickSort(num, iDown + 1, end);
	return 0;
}

[jimblumberg]

Please post the smallest complete program that illustrates your problem.

Jim

[RookieC++User]

jimblumberg, on 12 June 2011 - 11:23 AM, said:

Please post the smallest complete program that illustrates your problem.

Jim

I am going to assume you wanted the function that was giving me problems.

int Sort::utilQuickSort(int num[], int start, int end)
{
	if(start == end)
		return 0;
	
	if(start >= end)
		return 0;
	
	int iUp = start;
	int iDown = end;
	int iPivot = num[(start + end) / 2];

	cout << "Value of iPivot " << iPivot << endl;//Debug statement
	for(;;)/>
	{
		while(num[iUp] <= iPivot)
			iUp++;

		while(num[iDown] >= iPivot)
			iDown--;

		if(iUp <= iDown)
		{
			int tmp = num[iUp];
			num[iUp] = num[iDown];
			num[iDown] = tmp;
		}
		else
			break;
		cout << "Value of iUp " << iUp << endl;//Debug statement
		cout << "Value of iDown " << iDown << endl;//Debug statement
	};
	cout << "Value of num[iUp] " << num[iUp] << endl;//Debug statement
	cout << "Value of num[iDown] " << num[iDown] << endl;//Debug statement
	
	utilQuickSort(num, start, iDown - 1);
	//utilQuickSort(num, iDown + 1, end);
	return 0;
}

[jimblumberg]

No I wanted a program that I could compile and run to test the program.

Jim

[RookieC++User]

jimblumberg, on 12 June 2011 - 11:35 AM, said:

No I wanted a program that I could compile and run to test the program.

Jim

Here is the smallest program that I could make.

#include <iostream>
#include <ctime>
using namespace std;

int quickSort(int num[], int start, int end);

int main()
{
	srand(time(NULL));
	int * pArray;
	int size = 10;
	pArray = new int[size];

	for(int i = 0; i < size; i++)
		pArray[i] = rand() % 20 + 1;

	quickSort(pArray, 0, size - 1);

	for(int i = 0; i < size; i++)
		cout << pArray[i] << endl;
	return 0;
}

int quickSort(int num[], int start, int end)
{
	if(start == end)
		return 0;
	
	if(start >= end)
		return 0;
	
	int iUp = start;
	int iDown = end;
	int iPivot = num[(start + end) / 2];

	cout << "Value of iPivot " << iPivot << endl;//Debug statement
	for(;;)/>
	{
		while(num[iUp] <= iPivot)
			iUp++;

		while(num[iDown] >= iPivot)
			iDown--;

		if(iUp <= iDown)
		{
			int tmp = num[iUp];
			num[iUp] = num[iDown];
			num[iDown] = tmp;
		}
		else
			break;
		cout << "Value of iUp " << iUp << endl;//Debug statement
		cout << "Value of iDown " << iDown << endl;//Debug statement
	};
	cout << "Value of num[iUp] " << num[iUp] << endl;//Debug statement
	cout << "Value of num[iDown] " << num[iDown] << endl;//Debug statement
	
	quickSort(num, start, iDown - 1);
	//quickSort(num, iDown + 1, end);
	return 0;
}

[cabbae2]

This kinda looks to me like binary search with sorting added.

I found the original code for Binary Search maybe this could help:

void binarySearch(apvector <int> &array, int lowerbound, int upperbound, int key)
{
       int position;
       int comparisonCount = 1;    //count the number of comparisons (optional)

       // To start, find the subscript of the middle position.
       position = ( lowerbound + upperbound) / 2;

       while((array[position] != key) && (lowerbound <= upperbound))
       {
              comparisonCount++;
              if (array[position] > key)               // If the number is > key, ..
             {                                                       // decrease position by one.
                    upperbound = position - 1;   
             }                                                      
             else                                                
            {                                                        // Else, increase position by one.
                   lowerbound = position + 1;     
             }
             position = (lowerbound + upperbound) / 2;
       }
      if (lowerbound < = upperbound)
      {
            cout<< "The number was found in array subscript "<< position<<endl<<endl;
            cout<< "The binary search found the number after " << comparisonCount
                   << " comparisons.\n";             
            // printing the number of comparisons is optional
       }     
       else
             cout<< "Sorry, the number is not in this array.  The binary search made "
                   <<comparisonCount << " comparisons.";
       return;  // you may also consider returning the subscript
} 

I got it from here:link

I also found an explanation on quicksort with implementation in C++/Java here

This post has been edited by cabbae2: 12 June 2011 - 12:34 PM

[RookieC++User]

Has anybody made any progress with my problem? Because, I have looked it over again and still have not figured out my error.

[cabbae2]

Did you even look at the implementation of quicksort that I found for you which has a detailed explanation on how it works?

here it is:

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

 

      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

 

      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}

This post has been edited by cabbae2: 12 June 2011 - 08:47 PM

[RookieC++User]

Yes, I did look at the implementation you provided. I appreciate the fact that you provided that. But, I still have not found my error. So I must be just overlooking it.

[jimblumberg]

What is the purpose of your for loop?

Where are you incrementing iUp and decrementing iDown?

Jim

[cabbae2]

Let me tell you I did some editing to your code and I got it to work.

Here it is:

#include <iostream>
#include <ctime>
#include <math.h>
using namespace std;

void quickSort(int num[], int start, int end);
void printArray(int num[]);

int main()
{
	srand(time(NULL));
	int * pArray;
	int size = 10;
	pArray = new int[size];

	for(int i = 0; i < size; i++)
		pArray[i] = rand() % 20 + 1;
	printArray(pArray);

	quickSort(pArray, 0, size-1);


	for(int i = 0; i < size; i++)
		cout << pArray[i] << endl;

	cin.get();
	return 0;
}

void quickSort(int num[], int start, int end)
{
	int iUp = start, iDown = end;
	int	mid = (start + end) / 2;
	
	int iPivot = num[mid];

	cout << "Value of iPivot " << iPivot << endl;//Debug statement
	cout << "Start: " << start << " End: " << end << " Mid: " << mid << endl << endl;
	while(iUp < iDown)
	{
		while(num[iUp] < iPivot)
			iUp++;
		
		while(num[iDown] > iPivot)
			iDown--;
		

		cout << "iUp: " << iUp << " iDown: " << iDown << " Mid: " << mid << endl;

		if(iUp <= iDown)// Swapping in this if statement goes here.
		{
			int tmp = num[iUp];
			num[iUp] = num[iDown];
			num[iDown] = tmp;
			iUp++;
			iDown--;
		}
		printArray(num);
		cout << "Value of iUp " << iUp << endl;//Debug statement
		cout << "Value of iDown " << iDown << endl;//Debug statement
	};
	cout << "Value of num[iUp] " << num[iUp] << endl;//Debug statement
	cout << "Value of num[iDown] " << num[iDown] << endl;//Debug statement

	if (start < iDown)
		quickSort(num, start, iDown); 
	if (iUp < end)
		quickSort(num, iUp, end);
}

void printArray(int num[])
{
	for(int i = 0; i < 10; i++)
		cout << "[" << i << "] :" << num[i] << " ";

	cout <<endl;
}

Also what jimblumberg says is correct you did not modify the values of iUp or iDown and it was in an infinite loop.

jimblumberg, on 12 June 2011 - 09:27 PM, said:

Where are you incrementing iUp and decrementing iDown?

Jim

This post has been edited by cabbae2: 12 June 2011 - 10:21 PM

[RookieC++User]

I really appreciate both of you helping me. Thanks a lot. But, one last question. It should have never been an infinite loop, because my else statement was a break.

[cabbae2]

You are right about the break but even so that is malpractice.

RookieC++User, on 12 June 2011 - 10:40 PM, said:

I really appreciate both of you helping me. Thanks a lot. But, one last question. It should have never been an infinite loop, because my else statement was a break.