Page 1 of 1

Reputation:

# Recursive Quick Sort help

Posted 25 April 2010 - 10:38 PM

Hi all. I have to write a recursive quick sort algorithm for my C++ course and so far I've been trying to get the code working with a partition function that I wrote for a previous assignment but it keeps crashing for reasons I've been unable to track. Can I get a hand at why my code is failing?
```//Problem Assignment 8 Problem 1

#include <iostream>

using namespace std;

void swap (int& a, int& B)/> {
int temp = a;
a = b;
b = temp;
return;
}

void arrayPrint(int A[], int size) {
for (int i=0; i<size; i++) cout<<A[i]<<" ";
cout<<endl;
return;
}

int partition(int *A,int m,int n) {
int i=m;
if(n<1) return 0;
int j=n-1;
while (i<j) {
while (A[i]<=A[n-1] && i<j)
i++;
while (A[j]>=A[n-1] && i<j)
j--;
swap(A[i],A[j]);
}

if(A[i]>=A[n-1])  {
swap(A[i],A[n-1]);
return i;
}
else {
swap(A[i+1],A[n-1]);
return i+1;
}

}

void quickSort(int A[], int start, int end) {
int m;
if (start<end) {
m = partition(A, start, end);
quickSort(A, start, m-1);
quickSort(A, m+1, end);
}
return;
}

int main() {
int A[50] = {1,3,2,8,5,6,12,4,11,9,7};
quickSort(A,0,10);
arrayPrint(A,11);

return 0;
}

```

Is This A Good Question/Topic? 1

## Replies To: Recursive Quick Sort help

### #2 jaia

Reputation: 4
• Posts: 61
• Joined: 21-March 10

## Re: Recursive Quick Sort help

Posted 25 April 2010 - 11:04 PM

Check the capitalization in your Swap() function arguments. :-) Also, why do your void functions have return statements?

BTW, the program doesn't fully sort the list.

Reputation:

## Re: Recursive Quick Sort help

Posted 26 April 2010 - 01:16 AM

there's nothing wrong with the swap function's arguments; it's taking array values by reference
and i removed the redundant return statements.
i think my problem is currently the partition function. i'll be figuring out what's wrong but any help would be appreciated.

### #4 VariableScope

Reputation: 0
• Posts: 4
• Joined: 26-April 10

## Re: Recursive Quick Sort help

Posted 26 April 2010 - 02:08 AM

Ok I fixed the indices in the partition functiona and now it works perfectly.

The final code is this:
```//Jim Ramsey Khoury jr[dot]khoury[at]gmail[dot]com
//Quick Sort Algorithm with Partition function

#include <iostream>

using namespace std;

void swap (int& a, int& B)/> {
int temp = a;
a = b;
b = temp;
}

void arrayPrint(int A[], int size) {
for (int i=0; i<size; i++) cout<<A[i]<<" ";
cout<<endl;
}

int partition(int *A,int m,int n) {
int i=m;
if(n<1) return 0;
int j=n-1;
while (i<j) {
while (A[i]<=A[n] && i<j)
i++;
while (A[j]>=A[n] && i<j)
j--;
swap(A[i],A[j]);
}

if(A[i]>=A[n])  {
swap(A[i],A[n]);
return i;
}
else {
swap(A[i+1],A[n]);
return i+1;
}

}

void quickSort(int A[], int start, int end) {
int m;
if (start<end) {
m = partition(A, start, end);
quickSort(A, start, m-1);
quickSort(A, m+1, end);
}
}

int main() {
int A[50] = {1,3,2,8,5,6,12,4,11,9,7};
quickSort(A,0,10);
//partition(A,0,10);
arrayPrint(A,11);

return 0;
}

```

now works flawlessly

### #5 sri Harsha

Reputation: -1
• Posts: 6
• Joined: 19-April 10

## Re: Recursive Quick Sort help

Posted 26 April 2010 - 02:56 AM

VariableScope, on 26 April 2010 - 10:08 AM, said:

Hi all. I have to write a recursive quick sort algorithm for my C++ course and so far I've been trying to get the code working with a partition function that I wrote for a previous assignment but it keeps crashing for reasons I've been unable to track. Can I get a hand at why my code is failing?
```//Problem Assignment 8 Problem 1

#include <iostream>

using namespace std;

void swap (int& a, int& B)/> {
int temp = a;
a = b;
b = temp;
return;
}

void arrayPrint(int A[], int size) {
for (int i=0; i<size; i++) cout<<A[i]<<" ";
cout<<endl;
return;
}

int partition(int *A,int m,int n) {
int i=m;
if(n<1) return 0;
int j=n-1;
while (i<j) {
while (A[i]<=A[n-1] && i<j)
i++;
while (A[j]>=A[n-1] && i<j)
j--;
swap(A[i],A[j]);
}

if(A[i]>=A[n-1])  {
swap(A[i],A[n-1]);
return i;
}
else {
swap(A[i+1],A[n-1]);
return i+1;
}

}

void quickSort(int A[], int start, int end) {
int m;
if (start<end) {
m = partition(A, start, end);
quickSort(A, start, m-1);
quickSort(A, m+1, end);
}
return;
}

int main() {
int A[50] = {1,3,2,8,5,6,12,4,11,9,7};
quickSort(A,0,10);
arrayPrint(A,11);

return 0;
}

```

/execute this it may help u/

### #6 sri Harsha

Reputation: -1
• Posts: 6
• Joined: 19-April 10

## Re: Recursive Quick Sort help

Posted 26 April 2010 - 03:14 AM

```#include<stdio.h>
//#include<conio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/time.h>
#include<time.h>
int i;

struct timeval st_time,en_time;
double  ru_time;

//FUNCTION TO DISPLAY ARRAY
void disparr(int *a,int n)
{
printf("\nELEMENTS OF THE ARRAY ARE:");
for(i=0;i<n;i++)
{
printf("%d\t",*(a+i));
}
}

{
int range;
//randomize();
scanf("%d",&range);
for(i=0;i<n;i++)
{
*(a+i)=rand() %range;
}
}

int partition(int *a,int low,int high)
{
int pivot,temp,j;

pivot=a[low];
i=low;
j=high+1;

while(i<=j)
{
do
{
i=i+1;
}
while(pivot>=*(a+i));
do
{
j=j-1;
}
while(pivot<*(a+j));
if(i<j)
{
temp=*(a+i);
*(a+i)=*(a+j);
*(a+j)=temp;

}
}
temp=*(a+j);
*(a+j)=*(a+low);
*(a+low)=temp;
return j;
}

void   quick_sort(int *a,int low,int high)
{
int k;
if(low<high)
{
k=partition(a,low,high);       //partition the array into two sub arrays
quick_sort(a,low,k-1);         //sort the left part of the array
quick_sort(a,k+1,high);        //sort the right part of the array
}
}

//FUNCTION TO CHECK SORTING
int sort_check(int *a,int n)
{
int flag=0;
for(i=0;i<n;i++)
{
if(*(a+i)<*(a+i+1))
{
flag=-1;
break;
}
}
if(flag==0)
return 1;
else
return 0;
}
//MAIN
int main()
{
int *a,n,check,heap;

printf("\nENTER THE NUMBER OF ELEMENTS OF THE ARRAY:");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("\nUNSORTED ARRAY:");
disparr(a,n);
gettimeofday(&st_time,NULL);
quick_sort(a,0,n-1);

gettimeofday(&en_time,NULL);

check=sort_check(a,n);
if(check==0)

printf("\nELEMENTS ARE SORTED");

else
{
printf("\nELEMENTS ARE NOT SORTED");

}

ru_time=(en_time.tv_sec*1000+en_time.tv_usec/1000)- (st_time.tv_sec*1000+st_time.tv_usec/1000);

printf("\nSORTED ARRAY:");
disparr(a,n);
printf("runtime=%f",ru_time);

return 0;
}
```

This post has been edited by JackOfAllTrades: 26 April 2010 - 04:15 AM
Reason for edit:: Added code tags.

### #7 keithgarry

Reputation: 9
• Posts: 63
• Joined: 26-August 09

## Re: Recursive Quick Sort help

Posted 26 April 2010 - 04:41 AM

What exactly is the partition function doing to the numbers? I haven't worked much with algorithms yet and I'm having trouble running it through my head.

By the way, I'm not sure which IDE you're using, but in microsoft visual express 2008 arguments are case sensitive and I had to change B to b in order for it to run. Something to keep in mind I suppose.