thuattoan.dev

Level 1 · Cơ bản

Sắp xếp nhanh

Merge sort, quick sort — O(n log n).

Độ khó: Trung bình Visualizer tương tác7 bài luyện tập

Ý tưởng chính

Merge sort và quick sort dùng chiến lược chia để trị (divide and conquer) để đạt độ phức tạp O(n log n) trung bình.

Hình dung

Muốn sắp xếp 1.000 bài kiểm tra theo điểm? Chia đôi cho hai người, mỗi người lại chia đôi… đến khi mỗi xấp chỉ còn 1 bài. Sau đó gộp dần các xấp đã xếp lại với nhau — gộp hai xấp đã xếp thì rất dễ.

Cách hoạt động

  1. 1

    Merge sort: chia mảng làm đôi, sắp xếp từng nửa (đệ quy), rồi trộn hai nửa đã sắp xếp bằng cách so sánh phần tử đầu của mỗi nửa.

  2. 2

    Quick sort: chọn một phần tử làm pivot, dồn các phần tử nhỏ hơn pivot sang trái và lớn hơn sang phải.

  3. 3

    Pivot lúc này đã đứng đúng vị trí cuối cùng; tiếp tục quick sort cho hai phần hai bên.

  4. 4

    Cả hai đều là "chia để trị": bài toán lớn được chia thành bài toán nhỏ giống hệt nó.

Độ phức tạp

O(n log n). Merge sort luôn O(n log n) nhưng cần O(n) bộ nhớ phụ; quick sort trung bình O(n log n), xấu nhất O(n²) nếu chọn pivot tệ.

Khi nào dùng

Hầu như mọi lúc cần sắp xếp dữ liệu lớn. Trong thi đấu, thường chỉ cần gọi sort() của thư viện — nhưng hiểu cách nó chạy giúp bạn biến tấu (đếm nghịch thế, tìm phần tử thứ k…).

Lỗi hay gặp

  • Quick sort luôn chọn phần tử đầu/cuối làm pivot sẽ chậm O(n²) trên mảng đã sắp xếp sẵn.
  • Quên trường hợp dừng đệ quy (đoạn có ≤ 1 phần tử) gây lặp vô hạn.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

  • Lọc sản phẩm theo giá, đánh giá

    Trang thương mại điện tử sắp xếp hàng nghìn đến hàng triệu sản phẩm mỗi lần bạn đổi tiêu chí; O(n²) sẽ quá chậm.

  • Sắp xếp dữ liệu lớn hơn RAM

    Cơ sở dữ liệu dùng external merge sort cho ORDER BY trên bảng khổng lồ: chia thành các khối vừa bộ nhớ, sắp từng khối rồi trộn lại.

  • Gộp kết quả từ nhiều máy chủ

    Mỗi máy chủ trả về danh sách đã sắp xếp; bước merge trong merge sort ghép chúng thành một kết quả chung.

  • Hàm sort() bạn dùng hằng ngày

    Timsort của Python/Java là biến thể của merge sort; std::sort của C++ thường là introsort, dựa trên quick sort.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

  • Rating 1200

    Turtle and Good Pairs(mở Codeforces trong tab mới)

    Cho chuỗi s. Cặp (i, j) là 'tốt' nếu s_i = s_j, hoặc giữa chúng có vị trí k (i ≤ k < j) với s_k ≠ s_{k+1} và (s_k ≠ s_i hoặc s_{k+1} ≠ s_j). Sắp xếp lại s để số cặp tốt lớn nhất.

    Test mẫu & giải thích
    Input
    5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces
    Output
    acb
ddedf
urtlet
pppppppp
codeforces

    1. Test 1

      Với s="abc" (n=3, ba ký tự đôi một khác nhau), đáp án "acb" chỉ đạt được 1 cặp tốt: cặp (1,3) tốt vì chọn k=1 có s_1='a'≠s_2='c' và s_2='c'≠s_3='b' nên thỏa pleasant-pair; còn (1,2) và (2,3) không thể tốt vì đoạn con quá ngắn khiến k luôn trùng lặp với s_i hoặc s_{k+1} trùng s_j. Vì 3 ký tự đôi một khác nhau nên đây là giới hạn trên không thể vượt qua với mọi hoán vị — 'bac' hay 'cab' cũng là đáp án hợp lệ khác, không riêng 'acb'.

    2. Test 2

      Với s="edddf" (n=5), sắp xếp lại thành "ddedf" cho 6 cặp tốt: (1,2) và (2,4) tốt trực tiếp vì cùng ký tự 'd'; (1,5),(2,5),(3,5) tốt nhờ vị trí k=3 vì s_3='e'≠s_4='d' và 'e' khác cả s_1/s_2='d'; đây là số cặp tốt tối đa có thể đạt được với đa tập ký tự {d,d,d,e,f}.

  • Rating 1300

    Blue-Red Permutation(mở Codeforces trong tab mới)

    Cho mảng a, mỗi phần tử tô xanh hoặc đỏ. Mỗi bước giảm một phần tử xanh đi 1 hoặc tăng một phần tử đỏ lên 1. Hỏi có thể biến mảng thành một hoán vị của 1..n không.

    Test mẫu & giải thích
    Input
    8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
    Output
    YES
NO
YES
YES
NO
YES
YES
YES

    1. Test 1

      Chiến lược kiểm tra: sắp mảng tăng dần theo giá trị, phần tử xếp hạng thứ i (1-indexed) phải đổi được thành đúng giá trị i — phần tử đỏ (R, chỉ tăng) cần giá trị gốc ≤ i, phần tử xanh (B, chỉ giảm) cần giá trị gốc ≥ i. Test 1: a=[1,2,5,2] màu B,R,B,R, sắp theo giá trị được thứ tự 1(B),2(R),2(R),5(B) ứng hạng 1,2,3,4 — hạng1 xanh cần 1≥1 (đúng), hạng2,3 đỏ cần giá trị ≤2,≤3 (2 thỏa cả hai), hạng4 xanh cần 5≥4 (đúng); mọi ràng buộc đều thỏa nên in YES.

    2. Test 2

      a=[1,1] toàn màu B (chỉ giảm được), sắp theo giá trị được hạng1,2 đều giá trị 1 — hạng2 xanh cần giá trị ≥2 nhưng 1 chỉ có thể giảm chứ không tăng lên 2 được, vi phạm nên in NO.

  • Rating 1400

    Trinity(mở Codeforces trong tab mới)

    Cho mảng a. Mỗi thao tác gán a_i := a_j. Tìm số thao tác ít nhất để mọi bộ ba chỉ số khác nhau đều tạo thành một tam giác không suy biến.

    Test mẫu & giải thích
    Input
    4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7
    Output
    3
1
0
8

    1. Test 1

      Cách tính: sắp mảng tăng dần rồi tìm đoạn con liên tiếp dài nhất [l,r] sao cho hai phần tử nhỏ nhất trong đoạn có tổng lớn hơn phần tử lớn nhất a_r (khi đó mọi bộ ba trong đoạn đều tạo tam giác hợp lệ); các phần tử ngoài đoạn được gán lại bằng một giá trị trong đoạn, nên đáp án = n − (độ dài đoạn dài nhất đó). Test 1: a=[1..7] sau sắp xếp, đoạn {4,5,6,7} thỏa vì 4+5=9>7, nhưng mở rộng thêm phần tử 3 thì 3+4=7 không lớn hơn 7 (tam giác suy biến) nên đoạn dài nhất chỉ có 4 phần tử — đáp án 7−4=3.

    2. Test 2

      a=[1,3,2] sắp xếp thành [1,2,3], đoạn dài nhất thỏa chỉ có 2 phần tử {2,3} vì 1+2=3 không lớn hơn 3, nên đáp án 3−2=1.

  • Rating 1400

    Digital Logarithm(mở Codeforces trong tab mới)

    Cho hai mảng a, b cùng độ dài. Mỗi thao tác thay một phần tử x (ở mảng nào cũng được) bằng số chữ số của x. Tìm số thao tác ít nhất để hai mảng bằng nhau như hai tập bội (sắp xếp lại được).

    Test mẫu & giải thích
    Input
    4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169
    Output
    2
0
2
18

    1. Test 1

      Mỗi số có một dãy biến đổi cố định khi lặp lại phép lấy số chữ số: ví dụ 1000 → 4 (bốn chữ số) → 1 (một chữ số) → 1... (điểm bất động). Test 1: a=[1] đã ở điểm bất động, còn b=[1000] cần đúng 2 bước để về 1 (1000→4→1), nên tổng thao tác tối thiểu để hai mảng cùng bằng {1} là 2.

    2. Test 2

      a=[1,2,3,4] và b=[3,1,4,2] vốn đã là cùng một đa tập {1,2,3,4}, chỉ khác thứ tự phần tử, nên không cần thao tác nào — đáp án 0.

  • Rating 1400

    Swaps(mở Codeforces trong tab mới)

    Mảng a là hoán vị các số lẻ 1..2n−1, mảng b là hoán vị các số chẵn 2..2n. Mỗi thao tác đổi chỗ hai phần tử kề nhau trong một mảng. Tìm số thao tác ít nhất để a nhỏ hơn b theo thứ tự từ điển.

    Test mẫu & giải thích
    Input
    3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8
    Output
    0
2
3

    1. Test 1

      Vì a chỉ gồm số lẻ và b chỉ gồm số chẵn nên a_i luôn khác b_i ở mọi vị trí, do đó so sánh từ điển của toàn bộ dãy chỉ phụ thuộc vào cặp phần tử đầu tiên a_1 so với b_1. Test 1: a=[3,1], b=[4,2] đã có sẵn a_1=3<b_1=4 nên không cần đổi chỗ — đáp án 0.

    2. Test 2

      a=[5,3,1], b=[2,4,6] có a_1=5>b_1=2; để đạt a_1<b_1 rẻ nhất, đưa phần tử 1 (đang ở vị trí 3) lên đầu a bằng 2 lần đổi chỗ liền kề: [5,3,1]→[5,1,3]→[1,5,3], được a_1=1<b_1=2 — không có cách nào ít hơn 2 thao tác nên đáp án 2.

  • Rating 1600

    Tree Infection(mở Codeforces trong tab mới)

    Cho cây gốc 1, ban đầu mọi đỉnh khoẻ. Mỗi giây: (1) lây lan — với mỗi đỉnh có ít nhất một con bị nhiễm, được chọn thêm một con khác của nó để nhiễm; (2) tiêm — chọn một đỉnh bất kỳ để nhiễm. Tìm số giây ít nhất để cả cây bị nhiễm.

    Test mẫu & giải thích
    Input
    5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
    Output
    4
4
2
3
4

    1. Test 1

      Luật mỗi giây: trước tiên lan truyền — mọi đỉnh v đã có ít nhất một con nhiễm thì được nhiễm thêm đúng 1 con khác của v; sau đó tiêm — nhiễm tự do 1 đỉnh khoẻ bất kỳ, không cần kề với vùng đã nhiễm. Vì đỉnh gốc 1 không có cha nên bắt buộc phải nhiễm bằng tiêm. Test 1 (gốc 1 có con 2,3,4; đỉnh2 có con5,6; đỉnh4 có con7): giây1 tiêm đỉnh1; giây2 tiêm đỉnh2 (ưu tiên đỉnh nhiều con để tạo tiềm năng lan truyền); giây3 lan truyền từ đỉnh1 (đã có con2 nhiễm) sang đỉnh4, song song tiêm thẳng đỉnh5; giây4 lan truyền từ đỉnh1 sang đỉnh3 và từ đỉnh2 (đã có con5 nhiễm) sang đỉnh6, song song tiêm nốt đỉnh7 — đủ cả 7 đỉnh sau đúng 4 giây.

    2. Test 2

      Test 2 (chuỗi 1→4→5, đỉnh5 có con2,3): vì 1 và 4 chỉ có một con nên không tận dụng được lan truyền dọc chuỗi, nhưng có thể tiêm thẳng đỉnh2 ngay giây1 mà không cần đợi đỉnh5 nhiễm trước; giây2 nhờ đó lan truyền miễn phí từ đỉnh5 (đã có con2 nhiễm) sang đỉnh3, đồng thời tiêm đỉnh1; giây3,4 tiêm lần lượt đỉnh4 rồi đỉnh5 — tổng cộng vẫn cần 4 giây.

  • Rating 1700

    Yet Another Tournament(mở Codeforces trong tab mới)

    Có n đối thủ; đối thủ i thắng đối thủ j nếu i > j. Để thắng đối thủ i bạn cần chuẩn bị a_i phút, tổng cộng có m phút. Thứ hạng tính theo số trận thắng — tìm thứ hạng tốt nhất bạn đạt được.

    Test mẫu & giải thích
    Input
    5
4 401
100 100 200 1
3 2
1 2 3
5 0
1 1 1 1 1
4 0
0 1 1 1
4 4
1 2 2 1
    Output
    1
2
6
4
1

    1. Test 1

      Luật xếp hạng: đối thủ i thắng đối thủ j (i>j) mặc định, còn thắng bạn chỉ khi bạn bỏ ra ≥ a_i phút chuẩn bị, tổng thời gian chuẩn bị không vượt m; hạng của bạn = (số người có nhiều thắng hơn bạn) + 1. Test 1: n=4,m=401,a=[100,100,200,1], tổng a=401=m nên bạn chuẩn bị đủ cho cả 4 đối thủ, thắng cả 4 trận; trong khi đối thủ mạnh nhất (số4) cũng chỉ thắng tối đa 3 trận (trước các đối thủ 1,2,3), nên không ai thắng nhiều hơn bạn — hạng 1.

    2. Test 2

      n=3,m=2,a=[1,2,3], bạn chỉ đủ 2 phút để thắng đúng đối thủ 2 (a_2=2); kết quả đối thủ3 thắng cả bạn, đối thủ1 và đối thủ2 (vì 3>1,3>2 và bạn thua đối thủ3) nên có 3 thắng, còn bạn, đối thủ1, đối thủ2 đều có đúng 1 thắng — chỉ đối thủ3 hơn bạn nên hạng của bạn là 1+1=2.