Consider the following code:

#include <stdlib.h>
#include <time.h>

int main() {
    int n = 1000000000;

    int *a = malloc(sizeof(int) * n);
    srand((unsigned int)time(NULL));
    for (int i = 0; i < n; ++i) {
        int r = rand() % n;

        a[r] = r;
    }

    free(a);
}

When simply compiled with gcc test.c, it runs (according to time ./a.out) in 42 seconds on my machine. When I change a[r] = r to a[i] = r, it is much faster and takes only 15 seconds on my machine. Why does accessing random indices in the array take so much more time than accessing them in order? I expected both to take the same time.