В C почему замена x на y быстрее, чем замена y на x?

Question

В задаче минимум-свопы-2 , arr - несортированный массив, arr_count - количество элементов массива, нам нужно вернуть минимальное количество свопов для сортировки массива,

i попробовал:

int minimumSwaps(int arr_count, int* arr) {
    int swap = 0;
    for(int i  = 0; i < arr_count;){
        if(arr[i] != (i + 1)){
            int temp = arr[i];
            arr[i] = arr[arr[i] - 1];
            arr[arr[i] - 1] = temp;
            swap++;
        } else {
            i++;
        }
    }
    return swap;
}

но это не сработало. Это показывает ошибку тайм-аута. то есть, потребовалось больше времени, чтобы бежать! Затем я попробовал приведенный ниже код, он работал!

        int temp = arr[arr[i] - 1];
        arr[arr[i] - 1] = arr[i];
        arr[i] = temp;
        swap++;

Единственное различие между ними заключается в замене x на y или y на x. Какая разница?

Answer 1

После arr[i] = arr[arr[i] - 1]; значение arr[i] было изменено и arr[arr[i] - 1] больше не указывает на одно и то же хранилище, arr[arr[i] - 1] = temp; пишет в неправильное хранилище.

Таким образом, вы фактически не меняете два значения. Это может быть очевидно, если вы представляете его как арифметику указателя c.

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + *(arr + i) - 1) = temp;

Последняя строка равна *(arr + *(arr + temp - 1) - 1) со значениями, присутствующими в момент перед выполнением строки 2, что неверно по определению задачи.

На самом деле это дает очевидное решение:

        int temp = *(arr + i);
        *(arr + i) = *(arr + temp - 1);
        *(arr + temp - 1) = temp;

или

        int temp = arr[i];
        arr[i] = arr[temp - 1];
        arr[temp - 1] = temp;

Что дает результат 5, полученный от minimumSwaps.

По существу вы истекло время, потому что первый вариант не может найти решение.