My quick sort implementation doesn't work

Question

Can anyone help me with this code because when it's executed it doesn't sort correctly the array. I can't figure out what's wrong. I use this struct and get the data from a file

typedef struct record {
    int id_field;
    char string_field[20];
    int int_field;
    double double_field;
} record;

typedef int (*CompareFunction)(void *, void *);

and this is the quick sort:

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

void quick_sort(void **array, int left, int right, CompareFunction compare) {
   int index;
   if (left < right) {
      index = partition(array, left, right, compare);
      quick_sort(array, left, index - 1, compare);
      quick_sort(array, index + 1, right, compare);
   }
}

int partition(void **array, int left, int right, CompareFunction compare) {
  int pivot = left + (right - left) / 2;
  int i = left;
  int j = right;
  while (i < j) {
    if (compare(array[i], array[pivot]) < 0) {
        i++;
    } else {
        if (compare(array[j], array[pivot]) > 0) {
            j--;
        } else {
            swap(&array[i], &array[j]);
            i++;
            j--;
        }
     }
  }
  swap(&array[pivot], &array[j]);

  return j;
}

This is the compare function for int:

int compare_int_struct(void *ptr1, void *ptr2) {
    int i1 = (*((record *) ptr1)).int_field;
    int i2 = (*((record *) ptr2)).int_field;
    if (i1 < i2) {
        return -1;
    }
    if (i1 == i2) {
        return 0;
    }
    return 1;
 }

for example:

given array    sorted array
233460      |    233460
4741192     |    1014671
1014671     |    1188961
496325      |    3119429
4476757     |    496325
3754104     |    2146160
4271997     |    2163766
4896376     |    2369159
2735414     |    3754104
2163766     |    2735414
2369159     |    4271997
1188961     |    4476757
3843159     |    4741192
2146160     |    3843159

It seems it orders in small blocks

Answer 1

The problems are in your partition routine.

You are selecting a pivot index, you then proceed to partition the (sub)array by comparing values indirectly via this index, and the value identified by l or r, respectively.

However, as you go, swapping values, sooner or later your selected pivot value will change its position in the array and you're now comparing to whatever happens to wind up at the pivot index.

Instead, you should save off the pivot value and compare to that. This has the added benefit that it saves array indexing within the inner loops:

int partition(void **array, int left, int right, CompareFunction compare) {
  int pivot = left + (right - left) / 2;
  int pivotValue = array[pivot];  // ********
  int i = left;
  int j = right;
  while (i < j) {
    if (compare(array[i], pivotValue) < 0) {  // ********
        i++;
    } else {
        if (compare(array[j], pivotValue) > 0) {  // ********
            j--;
        } else {
            swap(&array[i], &array[j]);
            i++;
            j--;
        }
     }
  }
  swap(&array[pivot], &array[j]);

  return j;
}

And then there's that final swap. This is something you would use if you had chosen, up front, to move the selected pivot to the beginning or the end of the array and exclude that index from the remaining partitioning process. Several variants do this, but here that swap is just messing things up and should be removed.