Sắp Xếp Lẻ Giảm Bên Trái, Chẵn Tăng Bên Phải

Nguồn: Đề kiểm tra học kỳ 1 (câu c) Độ khó: Dễ Sắp xếp Hai con trỏ Chẵn lẻ

Đề bài

c) Sắp xếp mảng theo thứ tự: các số lẻ nằm về bên trái có thứ tự giảm dần, các số chẵn nằm về bên phải có thứ tự tăng dần (lưu ý: không dùng mảng phụ). In mảng kết quả ra màn hình. (1,5 điểm)

Ví dụ:

• Mảng ban đầu: $6, 5, 8, 12, 17, 8, 4, 3, 1, 5$
• Mảng đã sắp xếp: $17, 5, 5, 3, 1, 4, 6, 8, 8, 12$

Quy ước để chạy thử

Đề gốc là một câu trong đề kiểm tra, 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 1000)$, dòng sau là $n$ số nguyên $a_i$ $(|a_i| \le 10^9)$; in mảng kết quả trên một dòng, các số cách nhau một khoảng trắng.

Ví dụ – input

10
6 5 8 12 17 8 4 3 1 5

Ví dụ – output

17 5 5 3 1 4 6 8 8 12

Lời mở đầu

Bài này là câu c trong một đề kiểm tra học kỳ 1 trên trường, được một bạn học viên nhắn tin hỏi mình. Mình tổng hợp lại cuộc trò chuyện đó thành bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

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 6, 5, 8, 12, 17, 8, 4, 3, 1, 5 có các số lẻ là $5, 17, 3, 1, 5$ và các số chẵn là $6, 8, 12, 8, 4$. Xếp số lẻ về bên trái và giảm dần: $17, 5, 5, 3, 1$; số chẵn về bên phải và tăng dần: $4, 6, 8, 8, 12$. Ghép lại được đáp án 17, 5, 5, 3, 1, 4, 6, 8, 8, 12.

Điểm "ăn tiền" của câu này là dòng lưu ý không dùng mảng phụ. Bạn học viên hỏi mình cũng đang bí đúng chỗ đó. Mình sẽ đi từ cách dùng mảng phụ (dễ nghĩ nhưng không đạt yêu cầu) tới cách làm trực tiếp trên mảng ban đầu.

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ụ lẻ/chẵn · không đạt yêu cầuCách 2Hai con trỏ + sắp xếp từng đoạn · không mảng phụ

Cách 1Dùng 2 mảng phụ lẻ / chẵn

Đây là hướng mà bạn học viên định làm. "Dùng mảng phụ" nghĩa là: dùng 1 mảng đưa hết các số lẻ từ mảng hiện tại sang, sắp xếp mảng phụ đó cho các số lẻ giảm dần; rồi dùng tiếp 1 mảng phụ nữa đưa hết các số chẵn sang, sắp xếp cho các số chẵn tăng dần; sau đó đổ dữ liệu từ 2 mảng phụ vào lại mảng ban đầu (số lẻ trước, số chẵn sau).

Mình code nhanh hướng này cho các bạn tham khảo (sắp xếp dùng Interchange Sort, là thuật toán các bạn được học trên lớp):

#include <iostream>
using namespace std;

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void SortAscending(int *a, int n){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(a[i] > a[j]){
                Swap(a[i], a[j]);
            }
        }
    }
}

void SortDescending(int *a, int n){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(a[i] < a[j]){
                Swap(a[i], a[j]);
            }
        }
    }
}

void CreateArrayOddAndArrayEven(int *a, int n, int *ArrayOdd,
                                int &cntOdd, int *ArrayEven, int &cntEven){
    for(int i = 0; i < n; ++i){
        if(a[i] % 2 != 0){
            ArrayOdd[cntOdd++] = a[i];
        }
        else{
            ArrayEven[cntEven++] = a[i];
        }
    }
}

void SortOddToLeftAndDescendingAndEvenToRightAndAscending(int *a, int n){
    int ArrayOdd[1005], ArrayEven[1005];
    int cntOdd = 0, cntEven = 0;
    CreateArrayOddAndArrayEven(a, n, ArrayOdd, cntOdd, ArrayEven, cntEven);
    SortDescending(ArrayOdd, cntOdd);
    SortAscending(ArrayEven, cntEven);
    int idx = 0;
    for(int i = 0; i < cntOdd; ++i){
        a[idx++] = ArrayOdd[i];
    }
    for(int i = 0; i < cntEven; ++i){
        a[idx++] = ArrayEven[i];
    }
}

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

int main(){
    int n, a[1005];
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    SortOddToLeftAndDescendingAndEvenToRightAndAscending(a, n);
    PrintArray(a, n);
    return 0;
}

def SortAscending(a, n):
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]


def SortDescending(a, n):
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] < a[j]:
                a[i], a[j] = a[j], a[i]


def SortOddToLeftAndDescendingAndEvenToRightAndAscending(a, n):
    ArrayOdd = [x for x in a if x % 2 != 0]    # mảng phụ chứa số lẻ
    ArrayEven = [x for x in a if x % 2 == 0]   # mảng phụ chứa số chẵn
    SortDescending(ArrayOdd, len(ArrayOdd))
    SortAscending(ArrayEven, len(ArrayEven))
    a[:] = ArrayOdd + ArrayEven


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

Hàm CreateArrayOddAndArrayEven nhận cntOdd, cntEven bằng tham chiếu (int &) để sau khi gọi hàm, ở ngoài biết được mỗi mảng phụ có bao nhiêu phần tử.

Không gian$O(N)$ (2 mảng phụ)

Thời gian$O(N^2)$

Không đạt yêu cầu đề

Cách này dùng 2 mảng phụ ArrayOdd, ArrayEven nên vi phạm lưu ý "không dùng mảng phụ" của đề. Mình để ở đây cho các bạn so sánh, và dùng nó làm code đối chiếu khi kiểm tra cách 2.

Cách 2Hai con trỏ dồn lẻ/chẵn, rồi sắp xếp từng đoạn

Bài này cách làm thế này. Đầu tiên chưa nói gì đến sắp xếp cả: hãy cứ dồn hết số lẻ về bên trái, dồn hết số chẵn về bên phải. Muốn làm được thì ta dùng kỹ thuật hai con trỏ.

"Hai con trỏ" không phải con trỏ (pointer)

Bạn học viên hỏi mình: "không dùng kỹ thuật con trỏ có được không anh?". Hai con trỏ chỉ là tên gọi thôi, chứ nó không phải con trỏ (pointer) gì hết, chỉ là kỹ thuật đặt 2 biến index và cho chạy.

Bước 1: Dồn số lẻ về trái, số chẵn về phải

• Mảng có $N$ phần tử index từ $0$ đến $N - 1$. Đặt L = 0 là vị trí đầu tiên, R = N - 1 là vị trí cuối của mảng. Điều kiện lặp là L < R, chỉ dừng khi nào L >= R.
• Nguyên tắc: bên trái đang cần số lẻ, bên phải đang cần số chẵn. L duyệt từ trái qua phải, R duyệt từ phải qua trái.
• Nếu a[L] là số lẻ thì cứ L++ tiếp; đến khi gặp a[L] là số chẵn thì dừng lại tại đó.
• Rồi xét a[R]: là số chẵn thì cứ R-- tiếp; đến khi gặp a[R] là số lẻ thì dừng lại tại đó.
• Sau đó hoán vị a[L] và a[R], rồi quy tắc cứ thế lặp lại đến khi L >= R thì dừng.

Như vậy ta đã có mảng được đưa hết số lẻ về bên trái, số chẵn về bên phải. Lúc này các số lẻ và các số chẵn đang lộn xộn không có quy luật gì hết. Bước này chỉ có 1 vòng lặp, L và R đi từ 2 đầu vào nên tổng cộng $O(N)$.

Bước 2: Sắp xếp từng đoạn

Đồng thời ta cũng biết được có bao nhiêu số lẻ ($cntOdd$), bao nhiêu số chẵn, để biết vị trí bắt đầu và kết thúc của từng đoạn: đoạn số lẻ là $[0, cntOdd - 1]$, đoạn số chẵn là $[cntOdd, N - 1]$.

Rồi thì ta viết riêng hàm sắp xếp tăng dần và giảm dần. Nhưng bình thường hàm sắp xếp của các bạn sẽ duyệt i bắt đầu từ 0 và kết thúc ở $N - 1$ đúng không? Thì giờ hàm sắp xếp sẽ truyền vào start và finish, cho i = start chạy đến finish, coi như là sắp xếp trong đoạn từ start đến finish. Có start, finish của từng đoạn rồi thì gọi hàm sắp xếp truyền tương ứng vào thôi:

Tóm tắt

1. SwapOddToLeftAndEvenToRight(a, n): dồn lẻ trái, chẵn phải – $O(N)$.
2. cntOdd = CountElementOdd(a, n): đếm số lẻ – $O(N)$.
3. SortDescendingFromStartToFinish(a, 0, cntOdd - 1): đoạn lẻ giảm dần.
4. SortAscendingFromStartToFinish(a, cntOdd, n - 1): đoạn chẵn tăng dần.

Mọi thứ đều làm trực tiếp trên mảng a, không tạo thêm mảng phụ nào.

Minh hoạ

Ô tím là số lẻ, ô xanh dương là số chẵn, ô viền cam là các ô đang xét. Em nhập mảng rồi bấm Tiếp: phần đầu là bước dồn lẻ/chẵn bằng L, R; phần sau là sắp xếp từng đoạn (mỗi bước là một lượt i của Interchange Sort, chốt được 1 phần tử ở vị trí i):

Mảng a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void SortAscendingFromStartToFinish(int *a, int start, int finish){
    for(int i = start; i < finish; ++i){
        for(int j = i + 1; j <= finish; ++j){
            if(a[i] > a[j]){
                Swap(a[i], a[j]);
            }
        }
    }
}

void SortDescendingFromStartToFinish(int *a, int start, int finish){
    for(int i = start; i < finish; ++i){
        for(int j = i + 1; j <= finish; ++j){
            if(a[i] < a[j]){
                Swap(a[i], a[j]);
            }
        }
    }
}

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

void SwapOddToLeftAndEvenToRight(int *a, int n){
    int l = 0, r = n - 1;
    while(l < r){
        if(a[l] % 2 != 0){
            l++;
            continue;
        }
        if(a[r] % 2 == 0){
            r--;
            continue;
        }
        Swap(a[l], a[r]);
    }
}

int CountElementOdd(int *a, int n){
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        if(a[i] % 2 != 0){
            cnt++;
        }
    }
    return cnt;
}

int main(){
    int n, a[1005];
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    SwapOddToLeftAndEvenToRight(a, n);
    int cntOdd = CountElementOdd(a, n);
    SortDescendingFromStartToFinish(a, 0, cntOdd - 1);
    SortAscendingFromStartToFinish(a, cntOdd, n - 1);
    PrintArray(a, n);
    return 0;
}

def SortAscendingFromStartToFinish(a, start, finish):
    for i in range(start, finish):
        for j in range(i + 1, finish + 1):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]


def SortDescendingFromStartToFinish(a, start, finish):
    for i in range(start, finish):
        for j in range(i + 1, finish + 1):
            if a[i] < a[j]:
                a[i], a[j] = a[j], a[i]


def SwapOddToLeftAndEvenToRight(a, n):
    l, r = 0, n - 1
    while l < r:
        if a[l] % 2 != 0:
            l += 1
            continue
        if a[r] % 2 == 0:
            r -= 1
            continue
        a[l], a[r] = a[r], a[l]


def CountElementOdd(a, n):
    cnt = 0
    for i in range(n):
        if a[i] % 2 != 0:
            cnt += 1
    return cnt


n = int(input())
a = list(map(int, input().split()))
SwapOddToLeftAndEvenToRight(a, n)
cntOdd = CountElementOdd(a, n)
SortDescendingFromStartToFinish(a, 0, cntOdd - 1)
SortAscendingFromStartToFinish(a, cntOdd, n - 1)
print(*a)

Giải thích một số chỗ trong code ở trên:

1. Trong SwapOddToLeftAndEvenToRight, sau khi hoán vị mình không cần l++, r-- ngay, vì ở vòng lặp tiếp theo a[l] đã là số lẻ, a[r] đã là số chẵn nên tự nó sẽ tăng/giảm. Hai lệnh continue giúp quay lại kiểm tra điều kiện l < r sau mỗi lần dịch chuyển.
2. Kiểm tra số lẻ bằng a[i] % 2 != 0 chứ không phải a[i] % 2 == 1: trong C++ số âm lẻ chia 2 dư $-1$ (ví dụ $-3 \% 2 = -1$), viết == 1 là sai với số âm đó các bạn.
3. Nếu mảng không có số lẻ nào thì cntOdd - 1 = -1, vòng for(i = 0; i < -1; ...) không chạy lần nào nên vẫn đúng; tương tự khi không có số chẵn.
4. Mảng a[1005] trong main là mảng dữ liệu đầu vào chứ không phải mảng phụ. Bạn học viên cho biết đề học kỳ 1 chưa học con trỏ cấp phát động nên mình dùng mảng thường cho đúng kiến thức trên lớp.

C++▶ Chạy tay từng dòng codeDồn lẻ trái / chẵn phải bằng l, r; đếm số lẻ; Interchange Sort từng đoạn.

Dữ liệu vào (stdin) – sửa thoải mái10 6 5 8 12 17 8 4 3 1 5

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4void Swap(int &a, int &b){

5 int temp = a;

6 a = b;

7 b = temp;

8}

9

10void SortAscendingFromStartToFinish(int *a, int start, int finish){

11 for(int i = start; i < finish; ++i){

12 for(int j = i + 1; j <= finish; ++j){

13 if(a[i] > a[j]){

14 Swap(a[i], a[j]);

15 }

16 }

17 }

18}

19

20void SortDescendingFromStartToFinish(int *a, int start, int finish){

21 for(int i = start; i < finish; ++i){

22 for(int j = i + 1; j <= finish; ++j){

23 if(a[i] < a[j]){

24 Swap(a[i], a[j]);

25 }

26 }

27 }

28}

29

30void PrintArray(int *a, int n){

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

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

33 }

34}

35

36void SwapOddToLeftAndEvenToRight(int *a, int n){

37 int l = 0, r = n - 1;

38 while(l < r){

39 if(a[l] % 2 != 0){

40 l++;

41 continue;

42 }

43 if(a[r] % 2 == 0){

44 r--;

45 continue;

46 }

47 Swap(a[l], a[r]);

48 }

49}

50

51int CountElementOdd(int *a, int n){

52 int cnt = 0;

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

54 if(a[i] % 2 != 0){

55 cnt++;

56 }

57 }

58 return cnt;

59}

60

61int main(){

62 int n, a[1005];

63 cin >> n;

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

65 cin >> a[i];

66 }

67 SwapOddToLeftAndEvenToRight(a, n);

68 int cntOdd = CountElementOdd(a, n);

69 SortDescendingFromStartToFinish(a, 0, cntOdd - 1);

70 SortAscendingFromStartToFinish(a, cntOdd, n - 1);

71 PrintArray(a, n);

72 return 0;

73}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ làm việc trên mảng a, không tạo thêm mảng phụ nào ⇒ $O(1)$ bộ nhớ phụ, đáp ứng được yêu cầu của bài.
• Thời gian: bước dồn lẻ/chẵn dùng hai con trỏ duyệt từ 2 đầu mảng chạy vào ⇒ $O(N)$ vì chỉ lặp 1 vòng duy nhất qua $N$ phần tử. Bước sắp xếp mình cài nhanh theo Interchange Sort nên độ phức tạp thời gian khá tệ: $O(N^2)$. Tổng cộng $O(N^2)$.

Không gian$O(1)$

Thời gian$O(N^2)$

Muốn nhanh hơn thì sao?

Đề chỉ ràng buộc không dùng thêm mảng phụ, không hề quy định độ phức tạp thời gian, nên để nhanh gọn mình cài Interchange Sort cho đơn giản. Nếu đề có thêm yêu cầu sắp xếp tối ưu thì chỗ đó các bạn cài những thuật toán sắp xếp tốt hơn như Quick Sort (hoặc Heap Sort) để được $O(N \log N)$ nhé. Ví dụ trong C++ có sẵn sort(a, a + cntOdd, greater<int>()) và sort(a + cntOdd, a + n).

Một điểm chưa tối ưu

Bản chất code ở trên cũng chưa phải là tối ưu khi 2 hàm sắp xếp tăng/giảm từ Start đến Finish mình phải cài thành 2 hàm khác nhau, gần giống hệt nhau. Chỗ đó có thể chỉ cần viết 1 hàm làm được cả 2 chức năng nếu biết vận dụng kiến thức con trỏ hàm (Function Pointer). Tuy nhiên cái này vượt quá kiến thức học kỳ 1 nên mình không áp dụng kẻo các bạn bị rối, mốt học lên tiếp các bạn sẽ hiểu ^^

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ của đề, và đã được so với một chương trình đơn giản (lọc số lẻ sắp giảm, lọc số chẵn sắp tăng, ghép lại) trên 300 bộ test ngẫu nhiên có cả số âm, số 0 – khớp hết. Với $n = 1000$, C++ chạy khoảng 0,01 giây, Python cách 2 khoảng 0,07 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 😇