Recursive Quick Sort help

I can't fgure out where the recursion is failing

Page 1 of 1

6 Replies - 2277 Views - Last Post: 26 April 2010 - 04:41 AM Rate Topic: -----

#1 Guest_VariableScope*


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  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_VariableScope*


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.
Was This Post Helpful? 0

#4 VariableScope  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#5 sri Harsha  Icon User is offline

  • New D.I.C Head

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

Re: Recursive Quick Sort help

Posted 26 April 2010 - 02:56 AM

View PostVariableScope, 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/
Was This Post Helpful? 0
  • +
  • -

#6 sri Harsha  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • 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));
			}
	}


	//FUNCTION TO READ AN ARRAY
void readarr(int *a,int n)
	{
		int range;
		//randomize();
		printf("\nENTER YOUR RANGE:");
			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));
			readarr(a,n);
		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.

Was This Post Helpful? -1
  • +
  • -

#7 keithgarry  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1