[C] Esercizio su shift di array

[MItaly]

se per esempio decido di fare uno shift di 3 posizioni e il vettore e' di [6], gli ultimi 3 elementi del vettore vengono shiftati correttamente di 3 posizioni. i primi 3 invece non risultano shiftati e viene riportato nel print questo numero: -858993460

Stai sforando l'array in lettura: immagina di avere un array di N=10 elementi e dover shiftare di 5 posizioni; con i >= 5 vai a leggere da oltre la fine dell'array.

Per far funzionare un approccio di questo tipo dovresti come minimo fare il lookup in modulo (ovvero, (i + posizioni) % N), in modo che quando vai a leggere oltre la fine dell'array di fatto ricominci da capo. Tuttavia, anche questo sistema non funziona, perché quando ricominci a leggere dall'inizio stai rileggendo elementi che hai già sovrascritto. Una soluzione semplice può essere fare una copia dell'array originale e usare quella come input:

int rotate(int arr[], int N, int places) {
    int *copy = malloc(N*sizeof(*arr));
    places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
    for(int i = 0; i < N; ++i) copy[i] = arr[i];
    for(int i = 0; i < N; ++i) arr[i] = copy[(i + places + N) % N];
    free(copy);
}

Questa soluzione è O(N) in tempo e O(N) in spazio. Con poco più sforzo si può renderla O(N) in tempo e O(places) in spazio, copiando solo gli elementi che ci servono:

int rotate(int arr[], int N, int places) {
    places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
    int *copy = malloc(places*sizeof(*arr));
    for(int i = 0; i < places; ++i) copy[i] = arr[i];
    for(int i = 0; i < N; ++i) {
        int srcIdx = (i + places + N) % N;
        if(srcIdx < i) arr[i] = copy[srcIdx];
        else             arr[i] = arr[srcIdx];
    }
    free(copy);
}

Viceversa, la soluzione proposta da oregon è O(N*places) in tempo, ma O(1) in spazio (non serve storage aggiuntivo).

Va detto però che esiste una soluzione ottimale O(N) in tempo e O(1) in spazio, prova a pensarci...