按原点距离对坐标数组进行排序

Question

代码应该从用户处获取一个坐标数组，然后对该数组进行排序，将坐标按照与原点距离的顺序排列。我相信我的问题在于排序功能（我使用了快速排序）。

我在尝试自己编写函数以便更好地理解它，这就是为什么我不使用qsort()。

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define MAX_SIZE 64 

typedef struct 
{ 
    double x, y; 
}POINT; 

double distance(POINT p1, POINT p2); 
void sortpoints(double distances[MAX_SIZE], int firstindex, int lastindex, POINT data[MAX_SIZE]); 
void printpoints(POINT data[], int n_points); 

int main() 
{  
    int n_points, i; 
    POINT data[MAX_SIZE], origin = { 0, 0 }; 
    double distances[MAX_SIZE]; 

    printf("How many values would you like to enter?\n"); 
    scanf("%d", &n_points); 

    printf("enter your coordinates\n"); 

    for (i = 0; i < n_points; i++) 
    { 
     scanf("%lf %lf", &data[i].x, &data[i].y); 
     distances[i] = distance(data[i], origin); //data and distances is linked by their index number in both arrays 
    } 

    sortpoints(distances, 0, i, data); 

    return 0; 
} 

double distance(POINT p1, POINT p2) 
{ 
    return sqrt(pow((p1.x - p2.x), 2) + pow((p1.y - p2.y), 2)); 
} 

void printpoints(POINT *data, int n_points) 
{ 
    int i; 

    printf("Sorted points (according to distance from the origin):\n"); 

    for (i = 0; i < n_points; i++) 
    { 
     printf("%.2lf %.2lf\n", data[i].x, data[i].y); 
    } 
} 

//quicksort 
void sortpoints(double distances[MAX_SIZE], int firstindex, int lastindex, POINT data[MAX_SIZE]) 
{ 
    int indexleft = firstindex; 
    int indexright = lastindex; 
    int indexpivot = (int)((lastindex + 1)/2); 
    int n_points = lastindex + 1; 
    double left = distances[indexleft]; 
    double right = distances[indexright]; 
    double pivot = distances[indexpivot]; 
    POINT temp; 

    if (firstindex < lastindex) //this will halt the recursion of the sorting function once all the arrays are 1-size 
    { 

     while (indexleft < indexpivot || indexright > indexpivot) //this will stop the sorting once both selectors reach the pivot position 
     { 
      //reset the values of left and right for the iterations of this loop 
      left = distances[indexleft]; 
      right = distances[indexright]; 

      while (left < pivot) 
      { 
       indexleft++; 
       left = distances[indexleft]; 
      } 

      while (right > pivot) 
      { 
       indexright--; 
       right = distances[indexright]; 
      } 

      distances[indexright] = left; 
      distances[indexleft] = right; 

      temp = data[indexleft]; 
      data[indexleft] = data[indexright]; 
      data[indexright] = temp; 
     } 

     //recursive sorting to sort the sublists 
     sortpoints(distances, firstindex, indexpivot - 1, data); 
     sortpoints(distances, indexpivot + 1, lastindex, data); 
    } 

    printpoints(data, n_points); 
} 

感谢您的帮助，我一直试图调试几个小时，甚至使用调试器。

Answer 1

哎唷！您以i作为参数，致电sortpoints()。根据你的原型和代码，这个说法应该是last index，而i不是last index，而是last index + 1。

int indexleft = firstindex; 
int indexright = lastindex; // indexright is pointing to a non-existent element. 
int indexpivot = (int)((lastindex + 1)/2); 
int n_points = lastindex + 1; 
double left = distances[indexleft]; 
double right = distances[indexright]; // now right is an undefined value, or segfault. 

为了解决这个问题，请致电sortpoints()功能：

sortpoints (0, n_points-1, data); 

Answer 2

的问题是在你的sortpoints功能。第一个while循环无限循环。为了测试它是一个无限循环或不放置printf声明

printf("Testing first while loop\n"); 

在你的第一个while循环。你必须解决这个问题。

Answer 3

有相当多的问题，但其中之一是：

int indexpivot = (int)((lastindex + 1)/2); 

演员是不必要的，但是这琐事。更重要的是，如果你正在排序一个段，比如48..63，那么你将在元素32上旋转，这不在你应该工作的范围内。需要使用：

int indexpivot = (lastindex + firstindex)/2; 

或也许：

int indexpivot = (lastindex + firstindex + 1)/2; 

对于示例范围，这些将枢转元件55或56，它是至少的范围内上。

我强烈建议：

• 创建类似printpoints()，但有以下区别打印功能：

  1. 注意到一个“标签”字符串，以确定它是什么打印。
  2. 也打印距离数组。
  3. 获取阵列和一对偏移量。

• 在递归之前在排序函数中使用此函数。

• 返回前在排序函数中使用此函数。
• 阅读数据后，在主功能中使用此功能。
• 数据排序后，在主函数中使用此函数。
• 在适当的点打印关键值 - 枢轴距离，枢轴指数。

这使您可以检查您的分区是否正常工作（目前不在此处）。

然后，当代码正常工作时，您可以在排序功能中删除或禁用（注释掉）打印代码。