I need to implement quicksort algorithm for sorting an array with dynamically allocated memory. And I tried to write the code which work:

#include <stdio.h>
// function to swap elements
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}
// function to find the partition position
int partition(int array[], int low, int high) {
  // select the rightmost element as pivot
  int pivot = array[high];
  // pointer for greater element
  int i = (low - 1);
  // traverse each element of the array
  // compare them with the pivot
  for (int j = low; j < high; j  ) {
    if (array[j] <= pivot) {
      // if element smaller than pivot is found
      // swap it with the greater element pointed by i
      i  ;
      // swap element at i with element at j
      swap(&array[i], &array[j]);
    }
  }
  // swap the pivot element with the greater element at i
  swap(&array[i   1], &array[high]);
  // return the partition point
  return (i   1);
}
void quickSort(int array[], int low, int high) {
  if (low < high) {
    // find the pivot element such that
    // elements smaller than pivot are on left of pivot
    // elements greater than pivot are on right of pivot
    int pi = partition(array, low, high);
    // recursive call on the left of pivot
    quickSort(array, low, pi - 1);
    // recursive call on the right of pivot
    quickSort(array, pi   1, high);
  }
}
// function to print array elements
void printArray(int array[], int size) {
  for (int i = 0; i < size;   i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
// main function
int main() {
  size_t n = 8;
  int *x = malloc( n * sizeof( int ) );
  memcpy( x, ( int[] ){8, 7, 2, 1, 0, 9, 6,0}, n * sizeof( int ) ); // need <string.h>
  printf("Unsorted Array\n");
  printArray(x, n);
  // perform quick-sort on data
  quickSort(x, n);
  printf("Sorted array in ascending order: \n");
  printArray(x, n);
  free(x);
}

The problem is, the instruction was given to write the function as quickSort(int* x, int n) structure. But I was super confused then how the recursive function knew the left and right indices?

Another problem is, what's the best way to test my program? Like how to create test case efficiently. I am a mid level python developer and facing a lot of issue to work with C programming.

CodePudding user response：

Hint:

Passing (array, low, high) can be replaced by passing (array low, high - low), with the necessary adaptations.

For testing, fill an array of increasing values (possibly non-strictly). Generate all permutations of 1, 2, 3, 4 or 5 elements, sort and compare to the initial array (this is better than just checking increasing order, in case extra or duplicated values would be introduced !).

Also try a few permutations of several larger numbers of elements.

CodePudding user response：

In C, an array has its simplest possible form -- some fixed number of objects arranged contiguously in memory. In an array of int, for example, the addresses of those elements are sizeof(int) bytes apart.

When someone calls quicksort(int *x, int n), x is a pointer to the first element to sort, and n is the number of elements to sort. This could be an array, but it could also be part of an array.

In C, when you add 1 to an int *, it changes the address that the pointer points to by sizeof(int) bytes. This lets you use simple math to find other elements and make your recursive calls on parts of the input array.

For example:

• Sort the first 5 elements: quicksort(x,5)
• Sort the last 5 elements: quicksort(x n-5,5)
• Get the 7th element val = *(x 7); //equivalent to x[7]