Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C Linux
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
Edited 18-Feb-12 15:27pm
v3
Comments
Johannes Hillert at 18-Feb-12 21:23pm
   
Hello, just a question..
 
Your write:
 
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: bad
good
Please Sign up or sign in to vote.

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.
  Permalink  
v2
Rate this: bad
good
Please Sign up or sign in to vote.

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.
 
I hope, I could help you with this.
 
Cheers!
  Permalink  
v5
Comments
Johannes Hillert at 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!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 8,478
1 OriginalGriff 6,516
2 Peter Leow 3,567
3 Zoltán Zörgő 3,386
4 Richard MacCutchan 2,397


Advertise | Privacy | Mobile
Web04 | 2.8.150123.1 | Last Updated 19 Feb 2012
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100