Bài viết này trình bày hai bài toán cơ bản liên quan đến mảng: chèn một phần tử vào mảng đã được sắp xếp và di chuyển tất cả các số âm sang phía bên trái của mảng.

Chèn phần tử vào mảng đã sắp xếp

Giả sử chúng ta có một mảng được sắp xếp theo thứ tự tăng dần:

A = [3, 6, 9, 13, 17]
    

Chúng ta muốn chèn một số mới, ví dụ 10, sao cho mảng vẫn duy trì tính sắp xếp.

Kết quả mong muốn sau khi chèn là:

A = [3, 6, 9, 10, 13, 17]
    

Phân tích quy trình chèn từ nguyên tắc cơ bản

Bước 1: Bản chất của việc chèn

Chèn một phần tử đòi hỏi chúng ta phải tìm đúng vị trí, tạo một khoảng trống và đặt giá trị mới vào đó:

• Mảng ban đầu đã được sắp xếp tăng dần.
• Chúng ta cần tìm vị trí đầu tiên mà phần tử tại đó lớn hơn phần tử cần chèn.
• Di chuyển tất cả các phần tử từ vị trí đó về bên phải thêm một ô.
• Đặt phần tử mới vào ô trống vừa tạo.

Bước 2: Phân tích ví dụ

Mảng ban đầu:

A = [3, 6, 9, 13, 17]
n = 5 (số lượng phần tử)
    

Phần tử cần chèn: x = 10

1. Tìm vị trí chèn: Duyệt từ đầu mảng để tìm chỉ số i nhỏ nhất sao cho A[i] > x.
   • A[0] = 3: 10 > 3, tiếp tục.
   • A[1] = 6: 10 > 6, tiếp tục.
   • A[2] = 9: 10 > 9, tiếp tục.
   • A[3] = 13: 10 < 13, dừng lại. Vị trí chèn là i = 3.
2. Dịch chuyển phần tử: Bắt đầu từ phần tử cuối cùng, dịch chuyển các phần tử sang phải một ô để tạo khoảng trống tại vị trí i.
   • A[4] sang A[5]
   • A[3] sang A[4]
3. Chèn phần tử: Đặt 10 vào A[3].

Bước 3: Triển khai mã nguồn từng bước

#include <iostream>
#include <vector> // Sử dụng vector để dễ quản lý kích thước

int main() {
    std::vector<int> arr = {3, 6, 9, 13, 17}; // Mảng ban đầu
    int newValue = 10; // Giá trị cần chèn

    // Bước 1: Tìm vị trí chèn
    int insertPos = 0;
    while (insertPos < arr.size() && arr[insertPos] < newValue) {
        insertPos++;
    }

    // Bước 2: Tạo khoảng trống bằng cách dịch chuyển các phần tử
    // Thêm một phần tử giả ở cuối để có chỗ dịch chuyển
    arr.push_back(0); 
    for (int k = arr.size() - 1; k > insertPos; --k) {
        arr[k] = arr[k - 1];
    }

    // Bước 3: Chèn giá trị mới
    arr[insertPos] = newValue;

    // In kết quả
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}
    

Tối ưu hóa quy trình so sánh và dịch chuyển

Phương pháp ban đầu thực hiện hai bước riêng biệt: tìm vị trí rồi dịch chuyển. Chúng ta có thể kết hợp hai bước này để cải thiện hiệu quả.

Ý tưởng: Duyệt mảng từ cuối về đầu. Trong quá trình duyệt, nếu gặp phần tử lớn hơn giá trị cần chèn, hãy dịch chuyển nó sang phải một ô. Tiếp tục quá trình này cho đến khi gặp phần tử nhỏ hơn hoặc bằng giá trị cần chèn, hoặc đến đầu mảng. Vị trí ngay sau phần tử đó chính là vị trí chèn.

Bước 1: Triển khai mã nguồn tối ưu

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {3, 6, 9, 13, 17};
    int newValue = 10;

    // Thêm một phần tử giả ở cuối để có chỗ dịch chuyển
    arr.push_back(0); 

    int j = arr.size() - 2; // Bắt đầu từ phần tử cuối cùng thực tế

    // Duyệt từ cuối về đầu, vừa so sánh vừa dịch chuyển
    while (j >= 0 && arr[j] > newValue) {
        arr[j + 1] = arr[j]; // Dịch chuyển sang phải
        j--;
    }

    // Chèn giá trị mới vào vị trí đúng
    arr[j + 1] = newValue;

    // In kết quả
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}
    

Phân tích độ phức tạp:

• Trường hợp xấu nhất: Phần tử mới nhỏ hơn tất cả các phần tử trong mảng (ví dụ: chèn 1). Cần dịch chuyển tất cả n phần tử. Độ phức tạp: O(n).
• Trường hợp tốt nhất: Phần tử mới lớn hơn tất cả các phần tử trong mảng. Chèn trực tiếp vào cuối. Độ phức tạp: O(1).
• Trung bình, độ phức tạp vẫn là O(n), nhưng việc kết hợp hai thao tác giúp mã nguồn gọn gàng và có thể hiệu quả hơn trong thực tế.

Di chuyển số âm sang bên trái mảng

Cho một mảng các số nguyên, nhiệm vụ là di chuyển tất cả các số âm về phía bên trái và các số không âm (số 0 và số dương) về phía bên phải. Thứ tự tương đối của các phần tử trong mỗi nhóm không quan trọng.

Ví dụ:

A = {4, -2, 7, -9, 1, -5, 3}
    

Kết quả mong muốn (một trong các khả năng):

A = {-2, -9, -5, 4, 1, 7, 3}
    

Phân tích quy trình di chuyển từ nguyên tắc cơ bản

Bước 1: Xác định phần tử sai vị trí

• Một số âm nằm ở phía bên phải (gần cuối mảng) là sai vị trí.
• Một số không âm (>= 0) nằm ở phía bên trái (gần đầu mảng) là sai vị trí.

Chúng ta cần liên tục tìm các cặp "phần tử sai vị trí" và hoán đổi chúng.

Bước 2: Sử dụng hai con trỏ

Chiến lược hiệu quả là sử dụng hai con trỏ:

• Con trỏ left (hoặc i): Bắt đầu từ đầu mảng, di chuyển sang phải. Nó sẽ dừng lại ở phần tử không âm đầu tiên gặp phải (hoặc khi chạm con trỏ right).
• Con trỏ right (hoặc j): Bắt đầu từ cuối mảng, di chuyển sang trái. Nó sẽ dừng lại ở số âm đầu tiên gặp phải (hoặc khi chạm con trỏ left).

Bước 3: Logic với hai con trỏ

• Nếu A[left] < 0, nghĩa là số âm này đã ở đúng vị trí bên trái. Tăng left để xem phần tử tiếp theo.
• Nếu A[right] >= 0, nghĩa là số không âm này đã ở đúng vị trí bên phải. Giảm right để xem phần tử tiếp theo.
• Nếu cả hai điều kiện trên không đúng, nghĩa là chúng ta đã tìm thấy:
  • A[left] >= 0 (một số không âm ở vị trí sai bên trái)
  • A[right] < 0 (một số âm ở vị trí sai bên phải)
  Hoán đổi A[left] và A[right]. Sau đó, tăng left và giảm right để tiếp tục tìm kiếm.
• Quá trình kết thúc khi left >= right. Lúc này, mảng đã được phân chia thành hai phần: số âm bên trái và số không âm bên phải.

Bước 4: Triển khai mã nguồn

#include <iostream>
#include <vector>
#include <algorithm> // Sử dụng std::swap

void partitionNegatives(std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        // Di chuyển con trỏ trái qua các số âm
        while (left < right && arr[left] < 0) {
            left++;
        }

        // Di chuyển con trỏ phải qua các số không âm
        while (left < right && arr[right] >= 0) {
            right--;
        }

        // Nếu hai con trỏ chưa gặp nhau, hoán đổi các phần tử sai vị trí
        if (left < right) {
            std::swap(arr[left], arr[right]);
            // Sau khi hoán đổi, tiếp tục tìm kiếm
            left++;
            right--;
        }
    }
}

int main() {
    std::vector<int> arr = {4, -2, 7, -9, 1, -5, 3};

    partitionNegatives(arr);

    // In kết quả
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}
    

Phân tích độ phức tạp:

• Mỗi phần tử được xem xét bởi con trỏ left hoặc right tối đa một lần.
• Độ phức tạp thời gian: O(n), trong đó n là số lượng phần tử trong mảng.
• Độ phức tạp không gian: O(1) vì quá trình hoán đổi được thực hiện tại chỗ (in-place).