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

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只是传入的比较方法）。一切都很好，直到那时，在[C0 ]，并假设为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(...)不错，但我可能错了。最后是在文件中读取的2个示例：int：

lomuto

String：

5
4
3
2
1

Answer 1

这里未显示的主要问题是字符串的比较功能，转换问题。正确的版本应该是

uday
food
banana
apple
oranges

。由于使用的分区更加复杂，因此需要进行分区，因此我切换到了char *str1 = *((char**)a);上的另一个分区。我还从交换中删除了geeksforgeeks，因为在我眼中不需要，最后但并非最不重要的一点是，我没有正确解析数据以进行排序。意思是当我应该传入一个int数组时，我有一个字符串形式的数字列表。