# QuickSort Algorithm Assistance

Page 1 of 1

## 12 Replies - 653 Views - Last Post: 12 June 2011 - 10:58 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=235422&amp;s=aec640f7a7708aea921f6e7c68809bbc&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

# QuickSort Algorithm Assistance

Posted 12 June 2011 - 10:59 AM

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)
{
int	    last	    = size - 1;
int	    swap;

long int startSeconds = time(NULL);
// Perform the Bubble Sort algorithm
for (int pass=0; pass<size && swapMade; pass++)
{
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;
}
}
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;
}

```

Is This A Good Question/Topic? 0

## Replies To: QuickSort Algorithm Assistance

### #2 jimblumberg

Reputation: 3041
• Posts: 9,277
• Joined: 25-December 09

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 11:23 AM

Jim

### #3 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 11:29 AM

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

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;
}

```

### #4 jimblumberg

Reputation: 3041
• Posts: 9,277
• Joined: 25-December 09

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 11:35 AM

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

Jim

### #5 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 11:53 AM

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;
}

```

### #6 cabbae2

Reputation: -1
• Posts: 44
• Joined: 02-March 11

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 12:32 PM

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

### #7 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 08:22 PM

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

### #8 cabbae2

Reputation: -1
• Posts: 44
• Joined: 02-March 11

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 08:46 PM

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

### #9 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 09:08 PM

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.

### #10 jimblumberg

Reputation: 3041
• Posts: 9,277
• Joined: 25-December 09

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 09:27 PM

What is the purpose of your for loop?

Where are you incrementing iUp and decrementing iDown?

Jim

### #11 cabbae2

Reputation: -1
• Posts: 44
• Joined: 02-March 11

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 10:20 PM

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

### #12 RookieC++User

Reputation: 0
• Posts: 38
• Joined: 07-December 10

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 10:40 PM

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.

### #13 cabbae2

Reputation: -1
• Posts: 44
• Joined: 02-March 11

## Re: QuickSort Algorithm Assistance

Posted 12 June 2011 - 10:58 PM

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.