c - 按坐标到原点的距离对坐标数组进行排序

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()。根据您的原型(prototype)和代码，该参数应该是 last index，而 i 不是 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);