Sắp Xếp Chẵn Trái Lẻ Phải

Nguồn: Đề thi học phần CTDL và GT Độ khó: Dễ Sắp xếp Hai con trỏ Chẵn lẻ

Đề bài

Cho mảng số tự nhiên có $n$ phần tử. Viết hàm sắp xếp các phần tử có giá trị chẵn trong mảng sang phần bên trái (từ nhỏ đến lớn) và các phần tử có giá trị lẻ sang phần bên phải của mảng (từ nhỏ đến lớn).

Ví dụ: $\{2, 7, 6, 10, 9, 3\} \Rightarrow \{2, 6, 10, 3, 7, 9\}$.

(Đề gốc chỉ yêu cầu viết hàm, không nói định dạng vào/ra. Để chạy thử và kiểm tra, trong bài này mình quy ước: dòng đầu là $n$ $(1 \le n \le 10^5)$, dòng sau là $n$ số tự nhiên $a_i$ $(0 \le a_i \le 10^9)$; in ra mảng sau khi sắp xếp trên một dòng, các số cách nhau một khoảng trắng.)

Ví dụ – input

6
2 7 6 10 9 3

Ví dụ – output

2 6 10 3 7 9

Lời mở đầu

Trong quá trình đi comment dạo mình thấy bài tập này cũng hay nên chia sẻ lên đây để anh em cùng xem và thử sức nhé. Đây là câu hỏi của một bạn newbie đang ôn thi học phần Cấu trúc dữ liệu và Giải thuật: bạn ấy tính dùng cách tách mảng, nhưng vì là học phần CTDL và GT nên muốn dùng một thuật toán "xịn" hơn, kiểu như quicksort. Mình sẽ đưa ra cả hai hướng theo cách làm của mình để anh em cùng tham khảo và thảo luận hen. Hy vọng mang đến giá trị cho anh em 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ: mảng $\{2, 7, 6, 10, 9, 3\}$ có các số chẵn là $2, 6, 10$ và các số lẻ là $7, 9, 3$. Dồn các số chẵn về bên trái, sắp tăng dần: $2, 6, 10$; dồn các số lẻ về bên phải, sắp tăng dần: $3, 7, 9$ ⇒ kết quả $\{2, 6, 10, 3, 7, 9\}$. Lưu ý số $0$ cũng là số tự nhiên chẵn nhé.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tách 2 mảng phụ · O(N log N)Cách 2Hai con trỏ trên mảng gốc · O(N log N)

Cách 1Tách ra 2 mảng chẵn, lẻ – O(N log N)

Nếu đề bài chỉ là như vậy, không có yêu cầu ràng buộc gì thêm và đang trong ngữ cảnh phòng thi giới hạn thời gian thì chúng ta hãy chọn cách dễ dàng nhất:

• Tạo một mảng mới chứa các số chẵn, một mảng mới chứa các số lẻ.
• Sắp xếp 2 mảng đó tăng dần.
• Gán lại giá trị vào mảng ban đầu: các phần tử của mảng chẵn gán vào trước, tiếp đến mảng lẻ gán vào sau.

Như thế mảng gốc ban đầu sẽ có đúng trật tự như đề bài mong muốn. Cách này quá đơn giản rồi, code mẫu đây cho anh em nào mới học tham khảo:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), chan, le;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] % 2 == 0) {
            chan.push_back(a[i]);
        }
        else {
            le.push_back(a[i]);
        }
    }
    sort(chan.begin(), chan.end());
    sort(le.begin(), le.end());
    int k = 0;
    for(int i = 0; i < (int)chan.size(); i++) {
        a[k++] = chan[i];
    }
    for(int i = 0; i < (int)le.size(); i++) {
        a[k++] = le[i];
    }
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

n = int(input())
a = list(map(int, input().split()))
chan = sorted(x for x in a if x % 2 == 0)
le = sorted(x for x in a if x % 2 != 0)
a = chan + le
print(*a)

• Không gian: thêm 2 mảng phụ, tổng cộng $N$ phần tử ⇒ $O(N)$.
• Thời gian: tách mảng $O(N)$, sắp xếp $O(N \log N)$ ⇒ $O(N \log N)$.

Không gian$O(N)$ bộ nhớ phụ

Thời gian$O(N \log N)$

Cách 2Hai con trỏ left, right ngay trên mảng gốc – O(N log N)

Nhưng nếu đề bài có thêm ràng buộc là không được dùng thêm bộ nhớ bên ngoài, nói rõ hơn là không được tạo thêm các mảng trung gian mà chỉ được xử lý trên mảng gốc ban đầu; hoặc đề không ràng buộc nhưng chúng ta không có áp lực phòng thi gì cả, thì hãy thử sức bản thân theo hướng này. Nó hoàn toàn có thể giải quyết được mà không cần tạo ra các mảng phụ, chỉ xử lý trên duy nhất mảng gốc ban đầu là được.

Tư tưởng như sau:

• Tạo 2 biến left, right: left là chỉ số đầu tiên, right là chỉ số cuối cùng của mảng. left chạy từ đầu về cuối, right chạy từ cuối về đầu. left đại diện cho phần mảng số chẵn, right đại diện cho phần mảng số lẻ.
• Nếu phần tử tại mỗi biến đã đứng đúng chỗ (chẵn ở left, lẻ ở right) thì biến đó bỏ qua, xét phần tử tiếp theo. Nếu phát hiện phần tử đứng sai chỗ thì biến đó đứng lại tại đó.
• Khi cả hai đều đang đứng tại một phần tử sai chỗ (bên trái là số lẻ, bên phải là số chẵn) thì đổi chỗ 2 phần tử đó cho về đúng vị trí.
• Quy trình cứ thế lặp lại đến khi left >= right thì dừng, vì lúc này mỗi thằng đều đã đi hết phạm vi được phép của mình.

Giờ đây mảng gốc đã có các số chẵn dồn hết về đầu, số lẻ dồn hết về cuối, ta chỉ việc sắp xếp tăng dần trong phạm vi của mỗi đứa tụi nó thôi.

Ranh giới giữa 2 phần ở đâu?

Mỗi lần lặp, hoặc left tăng 1, hoặc right giảm 1, hoặc đổi chỗ (sau khi đổi thì a[left] chẵn nên lần lặp kế tiếp left sẽ tăng). Vì vậy vòng lặp dừng đúng lúc left == right. Phần tử tại vị trí gặp nhau này chưa được ai kiểm tra: nếu nó chẵn thì nó thuộc phần chẵn ⇒ phần chẵn là a[0..left], gồm left + 1 phần tử; nếu lẻ thì phần chẵn là a[0..left-1], gồm left phần tử. Đó chính là ý nghĩa của biến x trong code: số phần tử chẵn $= left + x$.

Đây chính là bước phân hoạch của Quicksort 😉

Bạn hỏi bài muốn dùng quicksort thì đây: hai con trỏ chạy từ hai đầu, gặp phần tử sai phía thì đứng lại rồi đổi chỗ, chính là bước phân hoạch (partition) kiểu Hoare của Quicksort. Chỉ khác là thay vì so với "chốt" (pivot), ta phân loại theo chẵn/lẻ. Còn bước sắp xếp từng phần, mình dùng hàm sort trong thư viện algorithm cho nhanh; nếu anh em tự code hàm sắp xếp (quicksort, mergesort…) thì cứ thay vào, miễn là cho phép sắp xếp trong một phạm vi cụ thể của mảng mà ta chủ động truyền tham số vào được.

Minh hoạ hai con trỏ

Em nhập mảng rồi bấm Tiếp để xem left, right chạy, đứng lại và đổi chỗ như thế nào:

Mảng a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (hàm Solve giữ nguyên như mình viết, chỉ thêm phần đọc dữ liệu cho dễ chạy thử):

#include <iostream>
#include <algorithm>
using namespace std;

int a[100005];

void Solve(int a[], int n) {
    int left = 0;
    int right = n - 1;
    while(left < right) {
        if(a[left] % 2 == 0) {
            left++;
            continue;
        }
        if(a[right] % 2 != 0) {
            right--;
            continue;
        }
        swap(a[left], a[right]);
    }
    int x = 0;
    if(a[left] % 2 == 0) {
        x = 1;
    }
    sort(a, a + left + x);
    sort(a + left + x, a + n);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    Solve(a, n);
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

def solve(a, n):
    left, right = 0, n - 1
    while left < right:
        if a[left] % 2 == 0:
            left += 1
            continue
        if a[right] % 2 != 0:
            right -= 1
            continue
        a[left], a[right] = a[right], a[left]
    x = 1 if a[left] % 2 == 0 else 0
    a[:left + x] = sorted(a[:left + x])
    a[left + x:] = sorted(a[left + x:])


n = int(input())
a = list(map(int, input().split()))
solve(a, n)
print(*a)

C++▶ Chạy tay từng dòng codeHai con trỏ dồn chẵn trái, lẻ phải ngay trên mảng gốc, rồi sort từng phần.

Dữ liệu vào (stdin) – sửa thoải mái6 2 7 6 10 9 3

Dữ liệu mẫu:

1#include <iostream>

2#include <algorithm>

3using namespace std;

4

5int a[100005];

6

7void Solve(int a[], int n) {

8 int left = 0;

9 int right = n - 1;

10 while(left < right) {

11 if(a[left] % 2 == 0) {

12 left++;

13 continue;

14 }

15 if(a[right] % 2 != 0) {

16 right--;

17 continue;

18 }

19 swap(a[left], a[right]);

20 }

21 int x = 0;

22 if(a[left] % 2 == 0) {

23 x = 1;

24 }

25 sort(a, a + left + x);

26 sort(a + left + x, a + n);

27}

28

29int main() {

30 int n;

31 cin >> n;

32 for(int i = 0; i < n; i++) {

33 cin >> a[i];

34 }

35 Solve(a, n);

36 for(int i = 0; i < n; i++) {

37 cout << a[i] << " ";

38 }

39 return 0;

40}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng vài biến left, right, x, không tạo mảng phụ nào ⇒ $O(1)$ bộ nhớ phụ (không tính mảng đầu vào).
• Thời gian: phần hai con trỏ mỗi bước đều thu hẹp khoảng $[left, right]$ (hoặc đổi chỗ rồi bước kế tiếp thu hẹp) ⇒ $O(N)$; phần sắp xếp $O(N \log N)$ ⇒ tổng $O(N \log N)$.

Không gian$O(1)$ bộ nhớ phụ

Thời gian$O(N \log N)$

Copy code từ điện thoại nhớ sửa dấu nháy

Code gốc mình soạn trên note điện thoại nên các dấu nháy “ ” và dấu — (thay vì --) sẽ bị sai khi copy vào máy tính. Code trong bài này đã được sửa lại chuẩn rồi, anh em cứ yên tâm dùng.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có cả số 0, toàn chẵn, toàn lẻ, $n = 1$), so với code vét cạn – khớp hết. Với $n = 10^5$ số ngẫu nhiên tới $10^9$: cả 2 cách bản C++ chạy khoảng 0.07 giây, bản Python khoảng 0.16 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇