Thuật toán đảo ngược để xoay mảng trong C

Khái niệm

Mảng: Bộ chứa các phần tử cùng kiểu, kích thước cố định.

Xoay mảng (Array rotation): Thay đổi thứ tự phần tử, dịch chỉ số, phần tử cuối về đầu.

Ví dụ: {3,6,8,1,4,10} xoay 2 lần → {4,10,3,6,8,1}

Thuật toán đảo ngược (Reversal Algorithm)

Chia mảng thành 2 mảng con, đảo từng mảng, ghép lại, đảo toàn bộ.

Input: mảng arr[], số vị trí xoay d, độ dài n
Bước 1: Tách thành a1[0..d-1] và a2[d..n-1]
Bước 2: Đảo ngược a1 và a2
Bước 3: Ghép a1 + a2
Bước 4: Đảo ngược mảng ghép → mảng đã xoay
Bước 5: In kết quả

Ví dụ minh họa

arr = {1,4,2,8,3,6,5}, d=3, n=7
a1 = {1,4,2}, a2 = {8,3,6,5}
a1 đảo = {2,4,1}, a2 đảo = {5,6,3,8}
Ghép: {2,4,1,5,6,3,8}
Đảo toàn bộ: {8,3,6,5,1,4,2} ← kết quả

Mã nguồn C

#include <stdio.h>

void reverse(int arr[], int start, int end) {
    int temp;
    while (start < end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++; end--;
    }
}

int main() {
    int arr[] = {54, 67, 12, 76, 25, 16, 34};
    int n = 7, d = 2;
    printf("Mảng ban đầu: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    reverse(arr, 0, d-1);
    reverse(arr, d, n-1);
    reverse(arr, 0, n-1);

    printf("\nMảng xoay trái %d phần tử: ", d);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Kết quả

Mảng ban đầu: 54 67 12 76 25 16 34
Mảng xoay trái 2 phần tử: 12 76 25 16 34 54 67