Доступ к элементам в массиве

Question

У меня есть модифицированная версия quicksort в моей программе, которой поручено сортировать pairs чисел на сумму их квадратов (например: -4,1 > 2,2). Моя программа отлично работает с positive integers, но когда я использую слишком много negative integers, программа вылетает (не более одного или двух отрицательных чисел приведет к сбою). Я думаю, что я пытаюсь использовать access или sort неопределенные части array, которые хранят integers. Что это за array хранения, которое я забываю? Или проблема в другом месте?

void swap(int *a,int *b); 
int square(int num); 
int abs_value(int num); 
void quicksort(int arr[],int first,int last); 

int main() 
{ 
    int num_of_pts; 
    int num1; 
    int num2; 
    printf("Enter number of points: ");//points are coordinates on the xy axis 
    scanf("%d", &num_of_pts);   //that's why there is double 
    int unsorted_pts_arr[2*num_of_pts];//the amount of storage in the array 
    for(int i=0; i<num_of_pts; i++){ 
     printf("Enter Point: "); 
     scanf(" %d",&num1); 
     scanf(" %d",&num2); 
     unsorted_pts_arr[2*i]=num1; 
     unsorted_pts_arr[2*i+1]=num2; 
    } 
    quicksort(unsorted_pts_arr,0,num_of_pts); 
    printf("Sorted Points:"); 
    for(int j=0; j<num_of_pts; j++) 
     printf(" (%d,%d)",unsorted_pts_arr[2*j],unsorted_pts_arr[2*j+1]); 
    return 0; 
} 

void swap(int *a,int *b) 
{ 
    int temp; 
    temp = *b; 
    *b = *a; 
    *a = temp; 
} 

int square(int num) 
{ 
    num=abs_value(num); 
    num*=num; 
    return num; 
} 

int abs_value(int num) 
{ 
    if(num<0) return -num; 
    else return num; 
} 

void quicksort(int arr[],int first,int last) 
{ 
    int pivot,j,i; 

    if(first<last){ 
     pivot=first; 
     i=first; 
     j=last; 

     while(i<j){ 
     while((square(arr[2*i])+square(arr[2*i+1]))<= 
       (square(arr[pivot])+square(arr[pivot+1])) 
       &&i<last) 
      i++; 
     while((square(arr[2*j])+square(arr[2*j+1]))> 
       (square(arr[pivot])+square(arr[pivot+1]))) 
      j--; 
     if(i<j){ 
      swap(&arr[2*i],&arr[2*j]); 
      swap(&arr[2*i+1],&arr[2*j+1]); 
     } 
     } 
     swap(&arr[pivot],&arr[2*j]); 
     swap(&arr[pivot+1],&arr[2*j+1]); 
     quicksort(arr,first,2*j-1); 
     quicksort(arr,2*j+1,last); 
    } 
} 

Answer 1

Главная проблема

Вы, скорее всего, доступ к массив из границ с помощью 2*j-1 и 2*j+1 как индексы массива в рекурсивных вызовов.

quicksort(arr,first,2*j-1); 
    quicksort(arr,2*j+1,last); 

При вызове quicksort из main, last равно num_of_pts. Имеет смысл, что в рекурсивных вызовах вы должны использовать j и j+1.

quicksort(arr,first,j); 
    quicksort(arr,j+1,last); 

Предложение для незначительного улучшения

Реализация square может быть проще.

int square(int num) 
{ 
    return num*num; 
} 

Answer 2

1. Индекс last является num_of_pts-1, так что

   quicksort(unsorted_pts_arr,0,num_of_pts); 
   

   должны лучше быть

   quicksort(unsorted_pts_arr, 0, num_of_pts-1); 
   

2. pivot используется как i и j к индексу пары чисел в arr , так она должна быть в два раза, а также:

      (square(arr[pivot])+square(arr[pivot+1])) 
   

   (оба вхождений) должны быть

      square(arr[2*pivot])+square(arr[2*pivot+1]) 
   

3. quicksort передается индексы для пар чисел (как в main), так что аргументы рекурсивного вызова также не должна быть удвоена:

    quicksort(arr,first,2*j-1); 
        quicksort(arr,2*j+1,last); 
   

   должен быть

    quicksort(arr, first, j-1); 
        quicksort(arr, j+1, last);