Getting segmentation fault while implementing quick sort

Question

I want to implement heap sort. For the purpose, I went through this http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L06-QuickSort.htm#basic tutorial and wrote the following code:

#include <stdio.h>


int quick_sort(int a[],int first,int last);

int main()
{
    int a[]= {12,3,4,23,1,7,9,34,89,45};
    int i;
    printf("Enter 10 integers: \n");

    for ( i = 0 ; i < 10 ; i++ )
    {
        scanf("%d",&a[i]);
        printf("\t%d\n",a[i]);
    }
    for ( i = 0 ; i < 10 ; i++ )
    {
        printf("\n%d ",a[i]);
    }
    quick_sort(a,0,9);

    for ( i = 0 ; i < 10 ; i++ )
    {
        printf("%d ",a[i]);
    }
    return 0;
}

int quick_sort(int a[],int first,int last)
{
    int i,j,pivot,temp ;

    if ( first - last <= 1 && first - last >= -1 )
    {
        return 0;
    }
    else
    {
        i = first ;
        j = last ;

        pivot = a[(i+j) / 2 ] ;

        while ( i != j )
        {
            while ( a[i] < pivot )
            {
                i++;
            }
            while( a[j] > pivot )
            {
                j--;
            }

            temp = a[i] ;
            a[i] = a[j] ;
            a[j] = temp ;
        }
    }
    quick_sort(a,0,i-1);
    quick_sort(a,j+1,9);
    return 0;

}

While running it using gcc compiler I am getting segmentation fault. Please help me to solve it.

Well, you are probably going out of bounds in one of your while loops. — Andro
– Andro, Commented May 22, 2014 at 19:05
if you run under a debugger you should find the line at which it is segfaulting. — dma
– dma, Commented May 22, 2014 at 20:07

Mahonri Moriancumer · Accepted Answer · 2014-05-22 20:28:11Z

1

There are several thing that in the question's quick_sort() function that are a mystery to me. Not that they are wrong; it's just that the purpose of various manipulations escapes me.

After working on it for a while, here is my version:

void quick_sort(int *a, int first, int last)
   {
   int i,j,pivot,temp;

   if(last <= 1)
       return;

   pivot = a[first + last/2];

   j = first + last/2;
   temp = a[first];
   a[first] = a[j];
   a[j] = temp;

   j = first;
   for(i = first+1; i < first+last; i++)
      {   
      if(a[i] < pivot)
         {
         j++;
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
         }
      }

   temp = a[first];    
   a[first] = a[j];
   a[j] = temp;

   quick_sort(a, first, j-first);
   quick_sort(a, j+1, first+last-j-1);
   return;
   }

Working spoiler testcase here.

answered May 22, 2014 at 20:28

Mahonri Moriancumer

6,0132 gold badges20 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jiminion · Accepted Answer · 2014-05-23 05:57:32Z

1

I'd try:

quick_sort(a,first,i-1);
quick_sort(a,j+1,last);

Instead of:

quick_sort(a,0,i-1);
quick_sort(a,j+1,9);

It at least allows the sort to work for lists different than 10 values....

You also need to check if i != j after every change, so I think that's problematic in your code as well. Or at least use i than j and the while would NEVER end.

edited May 23, 2014 at 5:57

answered May 22, 2014 at 19:31

Jiminion

5,1701 gold badge35 silver badges56 bronze badges

1 Comment

Jiminion Over a year ago

@user3641971, see added comment. I think you need to have check be i<j, not i!=j.

Collectives™ on Stack Overflow

Getting segmentation fault while implementing quick sort

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related