CODEWITHSUNDEEP
c++segmentation-faultquicksort
Dan
Dan

Reputation: 43

Why am I getting a segmentation fault on Quick Sort?

I'm getting a segmentation fault from running a quicksort algorithm. Here is my code

Sortings.h

    class Sortings {
     public:
      static void QuickSort(int* array, int size);
     private:
      static int partition(int* array, int l, int r);
      static void Quicksort_helper(int* array, int l, int r);
    };

Sortings.cpp

#include "Sortings.h"
void Sortings::QuickSort(int* array, int size){
  Quicksort_helper(array, 0, size);
}

int Sortings::partition(int* array, int l, int r){
  int p = array[l];
  int i = l;
  int j = r + 1;
  while (!(i <= j)){
    while (!(array[i] >= p))
      i = i+1;
    while (!(array[j] <=  p))
      j = j-1;
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  int temp2 = array[i];
  array[i] = array[j];
  array[j] = temp2;
  int temp3 = array[l];
  array[l] = array[j];
  array[j] = temp3;
  return j;
}

void Sortings::Quicksort_helper(int* array, int l, int r){
  if (l < r){
    int s = partition(array, l, r);
    Quicksort_helper(array, l, (s-1));
    Quicksort_helper(array, (s+1), r);
  }
}

In main.cpp I call Quicksort with an input array and size variable. Why is there a Segmentation fault when I run my main.cpp?

Upvotes: 0

Views: 270

Answers (2)

laune
laune

Reputation: 31290

The size is passed on to r and then there is indexing #

 int j = r + 1;
 ...
 while (!(array[j] <=  p))
     j = j-1;

If size really is "size", then you are out of the array.

Maybe:

Quicksort_helper(array, 0, size - 1);

Upvotes: 1

Gabe Sechan
Gabe Sechan

Reputation: 93542

You pass the size in as r. You set j=r+1. You loop for i=l to j. That's going out of bounds of your array. The valid bounds are [0,r-1]. You're looping until r+1. That's your issue.

Upvotes: 1

Related Questions