[jaia]

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.

[VariableScope]

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

[sri Harsha]

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/

[sri Harsha]

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

[keithgarry]

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.