13,293,894 members (63,100 online)
Rate this:
See more:
here is my code-but i am getting segmentation fault???? any body help me???
programme aim is:to find a time consumed[taken] for sorting a given array

#include<stdio.h>

#include<time.h>
const int MAX=1000;

int partition(int a[],int low,int high)
{
int i,j,temp,key;
key=a[low];
i=low;
j=high+1;
while(i<=j&&key<=a[i])
{
i++;
}
while(key>a[j])
{
j--;
}
if(i<j);>
{
temp=a[i],a[i]=a[j],a[j]=temp;
}
else
{
temp=a[low],a[low]=a[j],a[j]=a[low];
return j ;
}
}

void quick_sort(int a[],int low,int high)
{
int mid;
if(low<high)>
{
mid=partition(a,low,high);
quick_sort(a,low,mid-1);
quick_sort(a,mid+1,high);
}
}

void main()
{
int a[MAX],n,i,start,end;
//clock_t end,start;
double CLK_TCK;
printf("enter the no of elements:");
scanf("%d",&n);
printf("\n enter the elements to sort\n");
for(i=0;i<=n;i++)
scanf("%d",&a[i]);
start=clock();
quick_sort(a,0,n-1);
end=clock();
printf("n the sorted elemetns are:\n\n");
for(i=0;i<=n;i++)
printf("%d\t",a[i]);
printf("\n\n time consumed the array is: %5.2f sec: ",(end-start)/(double)CLK_TCK);
//getch();
} /<pre>

output: [which i tried,myfile name-quick_sort.c]
.........................................
subbu@subbu:~/Desktop\$ gcc quick_sort
subbu@subbu:~/Desktop\$ ./a.out
enter the no of elements:3

enter the elements to sort
2
3
3
2
Segmentation fault
subbu@subbu:~/Desktop\$
Posted 18-Feb-12 15:20pm
Updated 18-Feb-12 15:27pm
v3
Johannes Hillert 18-Feb-12 21:23pm

Hello, just a question..

printf("enter the no of elements:");
scanf("%d",&n);

And then:

for(i=0;i<=n;i++) scanf("%d",&a[i]);

Which will scan for n+1 inputs. Is that intended or did you mean:

for(i=0;i < n;i++) scanf("%d",&a[i]);

Rate this:

## Solution 1

There are a number of oddities in your posted code, it does not compile due to some errors I think are due to the posting script.
if(i<j);>

There's an extra ";>" in there. Also, later in the code,
if(low<high)>

Once I got rid of those, then this compiler warning might give you a clue as to why it blows up.

warning C4715: 'partition' : not all control paths return a value

It seems there's a way out of the "partition()" routine without returning a value so the value of "mid" would be garbage, which might lead to indexing beyond "MAX" which would then yield a segmentation fault.

I stepped through the code and at some point, "partition()" returned -858993460 so I decided to stop as this is clearly not right.
v2
Rate this:

## Solution 2

Hi,

I am sorry to tell you, but the segmentation fault probably comes from the many, many errors in your code. I got a stack overflow when I tried the code, but let's go through it.

Your main procedure is okay, but should look more like this:

void main()
{
int a[MAX], n, i;    // remove start and end here and
clock_t end, start;  // uncomment this again
// double CLK_TCK;  .. this you should not need, it's already defined

// [..]

for(i=0;i<n;++i)    // Use < here instead of <= or you ask for n+1 elements
scanf("%d",&a[i]);

// [..]

for(i=0;i<n;++i)    // Same as above..
printf("%d\t",a[i]);

// [..]
}

The quick_sort procedure is okay and seriously, I don't want to sound cocky or something, but the partition function is kinda messed up. Let's see:

int partition(int a[],int low,int high)
{
int i,j,temp,key;

/* key=a[low];  .. this does not make sense. Basically, you want the pivot element of the list here, the value of the element in the middle of your array, so.. */
key=a[(low+high)/2];  // use this instead.. btw. there are other methods to get the median, but this one works for most cases

i=low;
// j=high+1;  .. not sure why you add one to this, I would not do it as it complicates things
j=high;

/*
The rest of the function is problematic..

while(i <= j && key <= a[i])  .. the check i <= j and the use of a[i] in the second part would not have worked with j=high+1 .. what you want to do here is find the first element on the left side of the list that is BIGGER then your pivot element and go to the next index, if a[i] is less than your key value (a[i] < key)..
{
i++;
}

while(key > a[j])  .. j is used to iterate through the list from the right side of the pivot element until you find an element that is SMALLER than you key value, so you decrease j as long as a[j] > key... actually, I think, your checks work, too, if you intend to sort the list to have the largest element first and the smallest at the end of the final list
{
j--;
}

if(i<j)
{
temp=a[i],a[i]=a[j],a[j]=temp;
}
else      // .. I do not understand what you intended to do with this part.. if (i < j) than there is an element on the left side of the pivot element that is bigger than the one on the right side, so you swap the two elements to sort the list, like you do above. If the left element is smaller then the one on the right they are sorted. With the first part you move the larger element from the left side to the end and here you move the larger element to the beginning of the list and the smaller to the end..
{
temp=a[low],a[low]=a[j],a[j]=a[low];
return j ;  // also, this is your only return.. if you get the case (i<j) then there is no defined result for this function.
}
*/

/* So, this would be my suggestion on how the algorithm should look, if you want a list sorted from smallest to largest element that is */

while (i < j)
{
while (a[i] < key) ++i;
while (key < a[j]) --j;

if (i < j) temp = a[i], a[i] = a[j], a[j] = temp;
}

return i;
}

I suggest to analyze every state change when you develop an algorithm like this. I used a piece of paper for that and wrote down the variables used in loops for every iteration. This helps to find inconsistencies in your algorithms pretty quickly and often, you also get an idea on how to solve them that way, too.

Cheers!
v5
Johannes Hillert 19-Feb-12 0:11am

Man, next time I post something, I will copy it before I do so, half of what I wrote was gone after posting.. anyway, I wrote it again and hope it helps!

Top Experts
Last 24hrsThis month
 Jochen Arndt 340 OriginalGriff 308 Dave Kreskowiak 285 ppolymorphe 113 Dd129 100
 OriginalGriff 2,076 Jochen Arndt 1,130 Richard MacCutchan 1,040 ppolymorphe 899 CPallini 875