CODEWITHSUNDEEP
arrayscsegmentation-faultquicksort
Juan Connery
Juan Connery

Reputation: 41

Quicksort with pointers causing segfault

I'm trying to take the standard quicksort algorithm and slightly modify it by taking the partition function and making it so that instead of taking the entire array, a low index and a high index, it takes in a pointer to the low'th element as well as how many elements I want to partition. However, I'm getting a segmentation fault and I can't figure it out. Thanks for the help.

#include <stdio.h>

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

int partition(int *array, int high) {
  int pivot = array[high];
  int i = 0;

  for (int j = 0; j < high; j++) {
    if (array[j] <= pivot) {
      swap(&array[i++], &array[j]);
    }
  }

  swap(&array[i], &array[high]);
  return i;
}

void quickSort(int *array, int low, int high) {
  if (low < high) {
    int pi = partition(array + low, high - low);
    quickSort(array, low, pi - 1);
    quickSort(array, pi + 1, high);
  }
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int data[] = {8, 7, 2, 1, 0, 9, 6};
  
  int n = sizeof(data) / sizeof(data[0]);
  
  printf("Unsorted Array\n");
  printArray(data, n);
  
  // perform quicksort on data
  quickSort(data, 0, n - 1);
  
  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

Upvotes: 2

Views: 82

Answers (2)

rcgldr
rcgldr

Reputation: 28931

Alternate version of a pointer based quicksort using Hoare partition scheme:

void QuickSort(int *lo, int *hi)
{
int *i, *j;
int p, t;
    if(lo >= hi)
        return;
    p = *(lo + (hi-lo)/2);
    i = lo - 1;
    j = hi + 1;
    while (1){
        while (*(++i) < p);
        while (*(--j) > p);
            if (i >= j)
                break;
            t = *i;
            *i = *j;
            *j = t;
    }
    QuickSort(lo, j);
    QuickSort(j+1, hi);
}

Upvotes: 0

WhozCraig
WhozCraig

Reputation: 66254

Given the following in your code:

int pi = partition(array + low, high - low);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);

You're partitioning using a pointer-adjusted base (array+low), and segment pure length (high-low). That's fine if that is how your partition implementation works (most do). But you need to remember the resulting pivot location, pi, will be based on a position in that segment; not in the overall array. You need to adjust for that when recursing by putting back the original offset from whence that partition was configured:

int pi = partition(array + low, high - low);
quickSort(array, low, low + pi - 1);   // <== LOOK
quickSort(array, low + pi + 1, high);  // <== HERE

That change alone should get your implementation running. There are other ways to do this, and I'll update this answer with a couple of them when/if I find the time.

Upvotes: 3

Related Questions