Số dương ở vị trí chẵn, số âm ở vị trí lẻ (Thứ tự tương đối không giữ) trong C++

Trong bài toán này, cho một mảng, nhiệm vụ biến đổi mảng sao cho tất cả số dương ở chỉ số chẵn và số âm ở chỉ số lẻ.

Có thể số lượng số dương và âm không bằng nhau, trường hợp này không di chuyển các giá trị thừa.

Ví dụ minh họa:

Đầu vào - {3, 5, -1, 19, -7, -2}

Kết quả - {3, -1, 5, -7, 19, -2}

Để giải bài toán, tìm phần tử không đúng vị trí (dương không ở chẵn, âm không ở lẻ). Có nhiều cách, ở đây thảo luận hai phương pháp.

Phương pháp 1

Duyệt mảng, tìm lần đầu phần tử không đúng chỗ (dương ở lẻ hoặc âm ở chẵn) và hoán đổi chúng. Lặp cho đến khi duyệt hết mảng.

Chương trình minh họa

#include <iostream> 
using namespace std; 

void swapElements(int* a, int i, int j) { 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
    return; 
} 

void printArray(int* a, int n) { 
    for(int i = 0; i < n; i++) 
        cout << a[i] << "\t"; 
    cout << endl; 
    return; 
} 

void generateOrderedArray(int arr[], int n) { 
    for(int i = 0; i < n; i++) { 
        if(arr[i] >= 0 && i % 2 == 1) { 
            for(int j = i + 1; j < n; j++) { 
                if(arr[j] < 0 && j % 2 == 0) { 
                    swapElements(arr, i, j); 
                    break; 
                } 
            } 
        } else if(arr[i] < 0 && i % 2 == 0) { 
            for(int j = i + 1; j < n; j++) { 
                if(arr[j] >= 0 && j % 2 == 1) { 
                    swapElements(arr, i, j); 
                    break; 
                } 
            } 
        } 
    } 
    printArray(arr, n); 
} 

int main() { 
    int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 }; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "Mảng ban đầu: "; 
    printArray(arr, n); 
    cout << "Mảng sau khi sắp xếp (dương chẵn, âm lẻ): "; 
    generateOrderedArray(arr, n); 
    return 0; 
}

Kết quả

Mảng ban đầu: 3 5 -1 19 -7 -2 
Mảng sau khi sắp xếp (dương chẵn, âm lẻ): 3 -1 5 -7 19 -2

Phương pháp 2

Dùng kỹ thuật giống Quick Sort. Hai con trỏ: dương bắt đầu tại 0 (chẵn), âm tại 1 (lẻ). Tăng bước 2. Dừng khi con trỏ dương gặp số âm và con trỏ âm gặp số dương. Hoán đổi khi cả hai dừng. Nếu con trỏ nào ra khỏi mảng thì dừng.

Chương trình minh họa

#include <iostream> 
using namespace std; 

void swapElements(int* a, int i, int j) { 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
    return; 
} 

void printArray(int *a, int n) { 
    for (int i = 0; i < n; i++) 
        cout << a[i] << "\t"; 
    cout << endl; 
} 

void generateOrderedArray(int a[], int size) { 
    int positive = 0, negative = 1; 
    while (1) { 
        while (positive < size && a[positive] >= 0) 
            positive += 2; 
        while (negative < size && a[negative] <= 0) 
            negative += 2; 
        if (positive < size && negative < size) 
            swapElements(a, positive, negative); 
        else 
            break; 
    } 
} 

int main() { 
    int arr[] = { 3, 5, -1, 19, -7, -2 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Mảng ban đầu: "; 
    printArray(arr, n); 
    cout << "Mảng sau khi sắp xếp (dương chẵn, âm lẻ): "; 
    generateOrderedArray(arr, n); 
    printArray(arr, n); 
    return 0; 
}

Kết quả

Mảng ban đầu: 3 5 -1 19 -7 -2 
Mảng sau khi sắp xếp (dương chẵn, âm lẻ): 3 -1 5 -7 19 -2