Quicksort with pointers causing segfault

user_14267768 0
Viewed 59

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);
}
quicksort segmentation-fault c arrays
2 Answers

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.

user_13229720

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);
}
user_32820560
Related