Я получил разные результаты при использовании 2 разных компиляторов - PullRequest
Новая
       7

Я получил разные результаты при использовании 2 разных компиляторов

1 голос
/ 09 января 2020

У меня есть код, который меня смущает. Итак, я сделал исходный код, который будет делать некоторые разделы (точно так же, как быстрая сортировка), и слева и справа от pivot будут отсортированы. Но моя проблема в том, что, когда я отправляю его онлайн-судье, он дает мне неправильный ответ (но в моем коде я уже пробовал, он дает именно то, что должно быть на выходе). Это мой исходный код: 

#include "stdio.h"

int partition(int arr[],int left, int right);
void swap(int *a, int *b);
void quickSort(int arr[],int left, int right);

int main()
{
    int sizeArr,arr[1005], pv;
    scanf("%d",&sizeArr); getchar();

    for(int i = 0; i < sizeArr; i++){
        scanf("%d",&arr[i]); getchar();
    }

    pv = partition(arr,0,sizeArr);
    quickSort(arr,0,pv);
    quickSort(arr,pv + 1, sizeArr);

    printf("%d",arr[0]);
    for(int i = 1; i < sizeArr; i++) printf(" %d",arr[i]);
    printf("\n");

    return 0;
}

int partition(int arr[],int left, int right){
    int pv = left;
    if(left < right){
        pv = left;
        int l = left;
        int r = right + 1;
        do{
            do l++; while(arr[l] < arr[pv]);
            do r--; while(arr[r] > arr[pv]);
            if (l < r) swap(&arr[l],&arr[r]);
        } while(l < r);
        swap(&arr[pv],&arr[r]);
        return arr[pv];
    }
}

void quickSort(int arr[],int left, int right){
    if(left < right){
        int pv = left;
        int l = left;
        int r = right + 1;
        do{
            do l++; while(arr[l] < arr[pv]);
            do r--; while(arr[r] > arr[pv]);
            if (l < r) swap(&arr[l],&arr[r]);
        } while(l < r);
        swap(&arr[pv],&arr[r]);
        quickSort(arr, left, r - 1);
        quickSort(arr, r + 1, right);
    }
}

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

После моего расследования мой компилятор был G CC 4.9.2 32-разрядный выпуск, но онлайн-судья использует G CC 4.9.2 64-разрядный Релиз. Как мне решить мою проблему?

Вход 

5
4 5 3 7 2

Выход на G CC 4.9.2 64-разрядный выпуск: 

0 2 3 4 5

Выход на G CC 4.9.2 32-разрядная версия: 

2 3 4 5 7

1 Ответ

1 голос
/ 09 января 2020

когда left >= right, функция не будет возвращать значение: (см. Предложение в комментарии внизу.) 

int partition(int arr[],int left, int right){
    if(left < right){
        int pv = left;
        int l = left;
        int r = right + 1;
        do{
            do l++; while(arr[l] < arr[pv]);
            do r--; while(arr[r] > arr[pv]);
            if (l < r) swap(&arr[l],&arr[r]);
        } while(l < r);
        swap(&arr[pv],&arr[r]);
        return arr[pv];
    }
    // add a return statement here to remove all ambiguity
    // then test the return of this statement before using its results
}

... Что приведет к неожиданным результатам или, возможно, неопределенное поведение в этом вызове: 

pv = partition(arr,0,sizeArr);//pv may not be set properly here...
quickSort(arr,0,pv);//if pv is not set properly, unexpected
                    //results can occur here.

Как уже упоминалось в комментариях, предупреждения компилятора могут помочь вам уловить эти вещи рано. Установите предупреждения вашего компилятора на строжайший уровень. Например, я установил для моего предупреждения компилятора значение ALL (CLANG), и оно показало мне это в вашем коде:
enter image description here

...