Why is this quicksort algorithm implementation code getting Segmentation fault error?

Question

I am working on implementing the quicksort algorithm on c language.When i compile,it says segmentation fault and i cannot find the cause of it.I looked up GeeksForGeeks about quicksort and it is my attempt at it.

    #include<stdio.h>

    void swap(int *a,int *b){
        int temp=*a;
        *a=*b;
        *b=temp;
    }

    int partition(int arr[],int first,int last){
        int pivot=arr[last];
        int i=first-1;
        for(int j=first;j<=last-1;j++){
            if(arr[j]<=pivot){
            i++;
            swap(&arr[i],&arr[j]);
        }
     }
     swap(&arr[i+1],&arr[last]);
     return (i+1);
   }

   void quickSort(int arr[],int first,int last){
       int pivot=partition(arr,first,last);
       quickSort(arr,first,pivot-1);
       quickSort(arr,pivot+1,last);
   }



   int main() {
      int arr[]={1,8,3,9,4,5,7};
      int size=sizeof(arr)/sizeof(arr[0]);
      quickSort(arr,0,size-1);
      for(int i=0;i<size;i++){
          printf("%d ", arr[i]);
      }
   }

I was expecting to see 1 3 4 5 7 8 9 but i got Segmentation fault.

quickSort will always call quickSort which will always call quickSort which will always call quickSort which will always call quickSort which will always call quickSort which will always call quickSort, you have a recursion issue. — Hatted Rooster
– Hatted Rooster, Commented Jul 3, 2019 at 14:29
My compile even warns me: 'quickSort': recursive on all control paths, function will cause runtime stack overflow — Jabberwocky
– Jabberwocky, Commented Jul 3, 2019 at 14:29
Yes,thank you, i fixed it by adding if(first<last) inside the void quickSort(). — Ayano
– Ayano, Commented Jul 3, 2019 at 14:44

S.S. Anne · Accepted Answer · 2019-07-03 14:50:03Z

3

Inside quickSort, you need to check that first is less than last:

   void quickSort(int arr[],int first,int last)
   {
       if(first < last)
       {
           int pivot=partition(arr,first,last);
           quickSort(arr,first,pivot-1);
           quickSort(arr,pivot+1,last);
       }
   }

You might also give attribution to GeeksForGeeks, as this code looks extremely similar to theirs.

answered Jul 3, 2019 at 14:50

S.S. Anne

15.7k8 gold badges42 silver badges82 bronze badges

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

Comments

Paulo Vítor · Accepted Answer · 2019-07-03 20:07:33Z

0

You need to add a base case on quicksort() call, because on the way it's written it will call infinitely and leads to a segmentation fault.

answered Jul 3, 2019 at 20:07

Paulo Vítor

13 bronze badges

Collectives™ on Stack Overflow

Why is this quicksort algorithm implementation code getting Segmentation fault error?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related