wtf is wrong with this code???

chetan3191's Avatar, Join Date: Dec 2011
Light Poster
Code:
#include<stdio.h>
void quick(int[],int);

main(){
int a[]={11,2,5,4,7,3};
int len=sizeof(a)/sizeof(a[0]);
quick(a,len);

int i=0;
while(i<len){
printf("%d,",a[i]);
i++;
}
}





void quick(int a[],int len){

int pivot=a[0];
int loc=0;
int i=0,j=len-1;

while(i!=j){

while(j>=0 && i!=j ){
if(a[j]<pivot){
    printf("asdasdad");
a[loc]=a[j];
loc=j;
break;
}
j--;
}

while(a[i]<len && i!=j){
if(a[i]>pivot){    
a[loc]=a[i];
loc=i;
break;
}
i++;
}

}

a[i]=pivot;
}

copy this code and paste it in ur compiler...this is the first basic quick sort step...for the above given array elements this code goes into infinite loop and i am too stupid to understand the reason behind it.....kindly help me out guyzzz!!

Last edited by shabbir; 14Dec2011 at 09:04.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Code:
printf("asdasdad");
Well, you're on the right lines. But maybe you could print out something a bit more useful, say what it's doing and why, and display some variables, and do this in multiple places throughout the function. Then by inspecting the output you can - if you have placed enough debug printfs - find the cause of the problem. All we can tell from the current level of debug is that you're stuck in an infinite loop for some reason.
0
chetan3191's Avatar, Join Date: Dec 2011
Light Poster
that
printf("asdasdad");

is itself my debugging approach....i just need some1 to explain y it enters the infinite loop....
change the array elements to int a[]={4,3,2};

u will find that it gives an output without getting stuck!!

i'll myself even try to put printfs at various places....
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
>> "asdasdad" is itself my debugging approach

Yes I know. My point is that it's not sufficient.

>> .i just need some1 to explain y it enters the infinite loop

Sorry, the way to debug code is to learn to do it yourself, not just post it online and expect someone else to do it for you. I'll help you solve the problem yourself, but I won't spell it out for you.

>> 4,3,2 u will find that it gives an output without getting stuck!!

Yes, that's what makes debugging fun. Why does one array work ok and the other not? Maybe try swapping these around - see if you still get the problem. Does 3,4,2 work? Or add one: does 5,4,3,2 work? And so on.

>> i'll myself even try to put printfs at various places

Yep, that's what I do when I can't run the code in a debugger.
0
chetan3191's Avatar, Join Date: Dec 2011
Light Poster
in short...i will have to figure it out myself....thanx for the support!!
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Yes....but I'll help you figure it out for yourself. Post what you've got after you've sprinkled some printfs over the code and what ideas you might have about the cause of the problem.
0
Chong's Avatar, Join Date: May 2011
Go4Expert Member
Hi
It seems that your algorithm for quick sort is wrong. The following is the algorithm for quick sort. I hope this helps.
Best regards
Chong
Code:
+++++++++++++++++++++++++++++++++++++++++
// quicksort.cpp
//
//		This program shows how to use Quicksort to sort arrays.
//		Note that pivot in the program is nothing more than a guide!! It
//		is used just for a comparison!!
//

#include <stdio.h>
#include <string.h>
#include <conio.h> //for getche()
#include <windows.h>
#include <winbase.h>

#define		swap(x,y)	{ int t; t=x; x=y; y=t;}
#define		order(x,y)	if (x > y) swap(x,y)
#define		O2(x,y)		order(x,y)
#define		O3(x,y,z)	O2(x,y);O2(x,z);O2(y,z)

typedef enum {yes, no} yes_no;


static yes_no find_pivot(int *left, int *right, int *pivot_ptr);
static int *partition(int *left, int *right, int pivot);
void quicksort(int *left, int *right);


main( )
{
	int *p,pivot;
	int age[5] = {7,2,5,8,9};
	int len = sizeof(age)/sizeof(int);

	quicksort(age, age+len-1);

	for (int k=0; k<len; k++) {
		printf("[Age] %d\n", age[k]);
	} // for

	getche();

} // main


void quicksort(int *left, int *right)
{
	int *p;
	int pivot;

	if (find_pivot(left,right,&pivot) == yes) {
		p = partition(left,right,pivot);
		quicksort(left, p-1);
		quicksort(p, right);
	} // if

} // quicksort



static yes_no find_pivot(int *left, int *right, int *pivot_ptr)
{
	int a,b,c,*p;

	a = *left;
	b = *( left + (right-left)/2 );
	c = *right;

	O3(a,b,c);

	if (a < b) {
		*pivot_ptr = b;
		return (yes);
	} // if

	if (b < c) {
		*pivot_ptr = c;
		return(yes);
	} // if

	for ( p = left+1; p <= right; p++) {
		if (*p != *left) { 	
			*pivot_ptr = (*p < *left) ? *left: *p;
			return(yes);
		} // if
	} // for

	return(no);
} // find_pivot


static int *partition(int *left, int *right, int pivot)
{
	while (left <= right) {
		while (*left< pivot) ++left;
		while (*right >= pivot) --right;
		if (left < right) {
			swap(*left, *right);
			++left;
			--right;
		} // if
	} // while

	return(left);
} // partition

Last edited by shabbir; 24Dec2011 at 11:28.. Reason: Code blocks