Индекс проблем с функцией разделения в C - PullRequest
Новая
       5

Индекс проблем с функцией разделения в C

1 голос
/ 09 апреля 2020

Я пытался создать функцию разделения для быстрой сортировки, которую я хочу запустить на массиве созданной мной структуры. Однако во время выполнения индексы неожиданно ведут себя странно и безумно. (например, после определенного вызова bigger=bigger-1, bigger неожиданно получает значение 0 без видимой причины.

Это мой код: 

int partition(Student studentsArray[], int left, int right)
{
    Student tempArr[right+1 - left];
    int smaller = left; int bigger = right;
    for(int i =left; i<right;i++)
    {
        if(stringComperator(studentsArray[i].name,studentsArray[right].name)>0)
        {
            tempArr[bigger]=studentsArray[i];
            bigger=bigger-1;
        }
        else
        {
            tempArr[smaller]=studentsArray[i];
            smaller=smaller+1;
        }
    }
    tempArr[smaller]=studentsArray[right];
    for(int i=left;i<right-left+1;i++)
    {
        studentsArray[i]=tempArr[i];
    }
    return smaller;
}

edit : обновленный код: похоже, работает внутри метода, но похоже, что StudentsArray не изменит его значения вне вызова функции. 

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

int partition(Student studentsArray[], int left, int right)

{
    Student pivot = studentsArray[right];
    int i = left;
    for(int j = 0; j<right;j++)
    {
        if(stringComperator(studentsArray[j].name,pivot.name)<0)
        {
            swap(&studentsArray[i],&studentsArray[j]);
            i=i+1;
        }
    }
    swap(&studentsArray[i],&pivot);
    return i;
}

1 Ответ

1 голос
/ 09 апреля 2020

Ваш код имеет неопределенное поведение в таких строках, как: 

  tempArr[bigger]=studentsArray[i];

Ваш tempArr размер равен right+1 - left, а bigger начинается с равного right. Это означает, что когда left > 0, вы выходите за пределы.

Одна из многих вещей, которая может произойти в этих случаях, - это переопределение других c распределенных автоматических переменных, таких как bigger.

Несколько способов решить эту проблему, включая pedanti c, проверяющую размеры. Но, imho, простой способ - избежать создания tempArr и обновлять значения на месте.

...