无法通过使用指针算法对数组应用快速排序

Question

所以我一直在研究我的这个项目，但我似乎遇到了一个问题。从技术上讲，有 2 个问题，一个不会排序，两个我无法调试，因为我一直遇到段错误。我必须读入一个数据文件（字符串、整数或双精度数）。有了它，将它放在一个数组中，然后对其应用快速排序。数据类型已提供给我们，因此我们可以对数据应用正确的比较类型。虽然其余的有点朦胧。这是我到目前为止的代码：

/**
 * Swaps the values in two pointers.
 *
 * Casts the void pointers to character types and works with them as char
 * pointers for the remainder of the function.
 * Swaps one byte at a time, until all 'size' bytes have been swapped.
 * For example, if ints are passed in, size will be 4. Therefore, this function
 * swaps 4 bytes in a and b character pointers.
 */

static void swap(void *a, void *b, size_t size) {
  unsigned char * p = a, * q = b, tmp;
    for (size_t i = 0; i  < size; ++i)
    {
        tmp = p[i];
        p[i] = q[i];
        q[i] = tmp;
    }
}

/*
 * Partitions array around a pivot, utilizing the swap function.
 * Each time the function runs, the pivot is placed into the correct index of
 * the array in sorted order. All elements less than the pivot should
 * be to its left, and all elements greater than or equal to the pivot should be
 * to its right.
 * The function pointer is dereferenced when it is used.
 * Indexing into void *array does not work. All work must be performed with
 * pointer arithmetic.
 */
static int lomuto(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    char *ptr = array;
    int s = left;
    for (int i = left+1; i <= right; ++i){
      if( ((comp)( ptr+(i*elem_sz) , ptr+(left*elem_sz)  ))< 0 ){
        s++;
        swap( ptr+(s*elem_sz), ptr+(i*elem_sz), elem_sz);
      }
    }
    swap( ptr+(left*elem_sz), ptr+(s*elem_sz), elem_sz);
    return s;
}

/**
 * Sorts with lomuto partitioning, with recursive calls on each side of the
 * pivot.
 * This is the function that does the work, since it takes in both left and
 * right index values.
 */
static void quicksort_helper(void *array, int left, int right, size_t elem_sz,
                             int (*comp) (const void*, const void*)) {
   if (left < right){
        int pi = lomuto(array, left, right,elem_sz,comp); 

        quicksort_helper(array, left, pi-1,elem_sz,comp);  
        quicksort_helper(array, pi + 1, right,elem_sz,comp); 
    }
}


 /**
  * Quicksort function exposed to the user.
  * Calls quicksort_helper with left = 0 and right = len - 1.
  */
void quicksort(void *array, size_t len, size_t elem_sz,
               int (*comp) (const void*, const void*)) {
  quicksort_helper(array,0,len-1,elem_sz,comp);
}

我已读入输入数组并将其打印出来以验证是否所有内容都按应有的方式放入数组。然后我们进入 quicksort 方法，通过下面的 quicksort(list, i, sizeof(int),int_cmp); （如果你好奇 int_cmp 和其他 comp 只是传入的比较方法）。在那之前一切都很好，事情在 quicksort_helper 期间结束了，我假设 lomuto。我尝试在数组的开头打印 void *array 以查看是否出现任何明显错误。我这样做是通过：

char **int_array= (char **)array;
  for (int i = 0; i < 5; ++i){
     printf("A[%d] = %s\n",i,int_array[i]);
  }

尽管这会产生段错误 (printf(...))。我想说我的 lomuto 很好，但我可能是错的。最后是文件中读取的 2 个示例：整数：

字符串：

uday
food
banana
apple
oranges

Answer 1

这里没有显示的主要问题是字符串的比较函数，转换问题。正确的版本应该是char *str1 = *((char**)a);。除了使用的分区比它需要的更复杂，因此我切换到 geeksforgeeks 上的另一个分区。我不得不从交换中删除 unsigned，因为它不是在我眼中需要，最后但并非最不重要的一点是我没有正确解析数据以进行排序。这意味着当它们应该是传入的 int 数组时，我有一个字符串形式的数字列表。

无法通过使用指针算法对数组应用快速排序

Unable to apply quicksort on array via the usage of pointer arithmatic

c

arrays

pointers

void-pointers