Faire pivoter une matrice de 90 degrés

Problème : Étant donné une matrice ​\( N\times N \), faites-la pivoter de 90 degrés sur place. Sur place signifie une mémoire supplémentaire minimale à utiliser, c’est-à-dire ne pas créer de nouveau tableau à copier. Tourner dans le sens des aiguilles d’une montre signifie que la rangée du haut devient la colonne de droite, la colonne de droite devient la rangée du bas, etc.

Exemple :

\( M_{4,4} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 9 & 8 & 5 & 6 \\ 6 & 5 & 7 & 3 \\ 9 & 2 & 6 & 8 \end{pmatrix} \)\( \to \)​\( M^{\prime}_{4,4} = \begin{pmatrix} 9 & 6 & 9 & 1 \\ 2 & 5 & 8 & 2 \\ 6 & 3 & 5 & 3 \\ 8 & 7 & 6 & 4 \end{pmatrix} \)​

Solution : L’idée est de faire une variable d’échange “quadruple”, nous devons déplacer la valeur de haut\( \to \)​ droite, droite \( \to \)​ bas, bas \( \to \)​ gauche et gauche \( \to \)​ haut, pouvons-nous le faire en utilisant une seule variable supplémentaire ? Oui, c’est possible et nous le verrons plus bas.

A chaque couche, nous allons parcourir les éléments et les échanger comme suit :

1. Enregistrez l’élément i-ième dans le tableau de boucles dans une variable temporaire (dans notre exemple le tableau supérieur ​\( \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \).
2. Déplacez l’élément i-ième de la gauche vers le haut
3. Déplacez l’élément i-ième du bas vers la gauche
4. Déplace l’élément i-ième de la droite vers le bas
5. Enregistrer la valeur de notre variable temporaire dans la position i-ième dans le tableau de droite

Implémentation :

void rotateMatrix(int a[][]){
	
	int n = a.lenght;
	if (n <= 1){
		return // Rien a faire 
	}
	
	// Layer
	for (int i = 0; i < n; i++){
		// Elements
		for (int j = 0; i < n-i-1; j++){
			int saved = a[i][j];
			a[i][j] = a[n-j-1][i];
			a[n-j-1][i] = a[n-1-i][n-1-j];
			a[n-1-i][n-1-j] = a[j][n-1-i];
			a[j][n-1-i] = saved
		}
	}
	
}