thuattoan.dev

Level 1 · Cơ bản

Sắp xếp cơ bản

Bubble sort, selection sort, insertion sort — O(n²).

Độ khó: Dễ Visualizer tương tác8 bài luyện tập

Ý tưởng chính

Các thuật toán sắp xếp cơ bản dễ cài đặt nhưng có độ phức tạp O(n²), phù hợp để hiểu trực giác trước khi học các thuật toán nhanh hơn.

Hình dung

Giống xếp bài trên tay: bạn cầm từng lá mới và chèn nó vào đúng chỗ giữa những lá đã xếp. Hoặc giống xếp hàng theo chiều cao: cứ đổi chỗ hai bạn đứng cạnh nhau nếu bạn trước cao hơn.

Cách hoạt động

  1. 1

    Bubble sort: đi từ trái sang phải, gặp hai phần tử kề nhau sai thứ tự thì đổi chỗ. Sau mỗi lượt, phần tử lớn nhất "nổi" về cuối.

  2. 2

    Selection sort: mỗi lượt tìm phần tử nhỏ nhất trong phần chưa xếp, đưa nó lên đầu phần đó.

  3. 3

    Insertion sort: lấy lần lượt từng phần tử, dời các phần tử lớn hơn sang phải để chèn nó vào đúng vị trí trong phần đã xếp.

  4. 4

    Lặp lại cho đến khi không còn phần tử nào sai chỗ.

Độ phức tạp

O(n²) thời gian, O(1) bộ nhớ phụ. Insertion sort chỉ còn O(n) nếu mảng gần như đã sắp xếp.

Khi nào dùng

Mảng nhỏ (vài chục phần tử), dữ liệu gần như đã sắp xếp, hoặc khi cần hiểu bản chất của việc sắp xếp.

Lỗi hay gặp

  • Dùng cho n = 10⁵ trở lên: 10¹⁰ phép so sánh sẽ quá thời gian.
  • Viết sai cận vòng lặp (j < n − 1 − i) làm truy cập ra ngoài mảng.

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.

  • Xếp bài trên tay

    Khi bốc từng lá bài và chèn vào đúng chỗ giữa các lá đã xếp, bạn đang làm đúng insertion sort.

  • Bên trong hàm sort() của thư viện

    Với đoạn dữ liệu nhỏ hoặc gần như đã sắp xếp, insertion sort chạy rất nhanh nên Timsort (Python, Java) và std::sort (C++) dùng nó cho các đoạn ngắn.

  • Bảng xếp hạng cập nhật liên tục

    Khi một người chơi vừa tăng điểm, chỉ cần đẩy họ lên vài bậc bằng các phép so sánh–đổi chỗ kề nhau thay vì sắp xếp lại toàn bộ.

  • Thiết bị nhúng ít bộ nhớ

    Các thuật toán này sắp xếp tại chỗ, gần như không cần bộ nhớ phụ, phù hợp vi điều khiển có vài KB RAM.

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 800

    My First Sorting Problem(mở Codeforces trong tab mới)

    Cho hai số nguyên x và y. In ra số nhỏ hơn trước, rồi đến số lớn hơn.

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

    1. Test 1

      Với cặp đầu tiên x=1, y=9: 1 đã nhỏ hơn 9 nên in nguyên "1 9".

    2. Test 2

      Với cặp thứ hai x=8, y=4: số nhỏ hơn là 4 nên in 4 trước rồi đến 8, cho ra "4 8".

  • Rating 800

    Replacing Elements(mở Codeforces trong tab mới)

    Cho mảng a và số d. Mỗi thao tác chọn ba chỉ số khác nhau i, j, k và gán a_i = a_j + a_k. Hỏi có thể làm cho mọi phần tử đều ≤ d hay không.

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

    1. Test 1

      n=5, d=3, a=[2,3,2,5,4]. Các phần tử đã ≤ d=3 chỉ gồm {2,3,2}; hai phần tử nhỏ nhất trong nhóm này là 2 và 2, tổng bằng 4 > 3, nên bất kỳ phần tử nào được gán bằng tổng của hai phần tử khác cũng tối thiểu là 4 > d, không thể kéo 5 và 4 xuống ≤3 → NO.

    2. Test 2

      n=3, d=4, a=[2,4,4], mọi phần tử đã ≤4 sẵn nên không cần thao tác nào, thỏa điều kiện ngay → YES.

  • Rating 800

    Sorting Parts(mở Codeforces trong tab mới)

    Cho mảng a. Bạn chọn một độ dài len (1 ≤ len < n), sắp xếp riêng tiền tố độ dài len và hậu tố còn lại. Hỏi có cách chọn nào khiến mảng sau đó vẫn KHÔNG tăng dần không (YES/NO).

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

    1. Test 1

      n=3, a=[2,2,1]. Chọn len=1: tiền tố [2] giữ nguyên (đã "sắp xếp" vì chỉ 1 phần tử), hậu tố [2,1] sắp lại thành [1,2], mảng kết quả là [2,1,2], vẫn có 2>1 nên không tăng dần → YES.

    2. Test 2

      n=4, a=[3,1,2,1], cũng chọn len=1: tiền tố [3] giữ nguyên, hậu tố [1,2,1] sắp lại thành [1,1,2], kết quả [3,1,1,2] vẫn có 3>1 nên không tăng dần → YES.

  • Rating 800

    Bazoka and Mocha's Array(mở Codeforces trong tab mới)

    Cho mảng a. Mỗi thao tác tách a thành tiền tố x và hậu tố y rồi đổi thành y + x. Hỏi sau một số thao tác bất kỳ, mảng có thể trở thành không giảm hay không.

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

    1. Test 1

      n=6, a=[1,1,4,5,1,4]. Thử các cách tách: tách x=[1,1,4,5], y=[1,4] được [1,4,1,1,4,5]; tách x=[1,1,4], y=[5,1,4] được [5,1,4,1,1,4]; các cách tách còn lại cũng đều để lại ít nhất một chỗ số sau nhỏ hơn số trước, và làm thêm thao tác trên các dãy đó cũng chỉ quay về những dãy như vậy → No.

    2. Test 2

      n=5, a=[7,9,2,2,3]. Tách x=[7,9], y=[2,2,3] rồi đổi thành y + x = [2,2,3,7,9], dãy không giảm → Yes.

  • Rating 800

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

    Cho mảng a. Tìm cặp chỉ số (i, j) sao cho với mọi k: |a_i − a_k| + |a_k − a_j| = |a_i − a_j|. In ra một cặp bất kỳ.

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

    1. Test 1

      Điều kiện |a_i-a_k|+|a_k-a_j|=|a_i-a_j| đúng với mọi k tương đương a_k phải nằm giữa a_i và a_j (theo giá trị) với mọi k, nên cặp (i,j) hợp lệ chính là chỉ số của giá trị nhỏ nhất và lớn nhất trong mảng. Test 1: a=[5,2,7], giá trị nhỏ nhất 2 ở chỉ số 2, lớn nhất 7 ở chỉ số 3, nên in "2 3".

    2. Test 2

      a=[1,4,2,2,3], nhỏ nhất 1 ở chỉ số 1, lớn nhất 4 ở chỉ số 2, nên in "1 2".

  • Rating 800

    Gamer Hemose(mở Codeforces trong tab mới)

    Có n vũ khí, vũ khí i gây a_i sát thương; kẻ địch có H máu. Mỗi lượt dùng một vũ khí, nhưng không được dùng cùng một vũ khí hai lượt liên tiếp. Tìm số lượt ít nhất để máu kẻ địch ≤ 0.

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

    1. Test 1

      n=2, H=4, a=[3,7]. Lượt đầu tiên không bị ràng buộc gì vì chưa dùng vũ khí nào trước đó, nên chọn vũ khí gây sát thương lớn nhất là 7 ≥ 4 = H, hạ gục kẻ địch ngay trong 1 lượt.

    2. Test 2

      n=2, H=6, a=[4,2]. Vũ khí mạnh nhất chỉ gây 4 < 6 nên không thể xong trong 1 lượt; dùng vũ khí 1 (4 sát thương) rồi bắt buộc đổi sang vũ khí 2 (2 sát thương) vì không được dùng liên tiếp cùng một vũ khí, tổng 4+2=6 ≥ 6 nên cần đúng 2 lượt.

  • Rating 1000

    Olya and Game with Arrays(mở Codeforces trong tab mới)

    Có n mảng, mỗi mảng ít nhất 2 phần tử. Từ mỗi mảng được chuyển tối đa một phần tử sang mảng khác. Độ đẹp là tổng phần tử nhỏ nhất của các mảng — tìm độ đẹp lớn nhất.

    Test mẫu & giải thích
    Input
    3
2
2
1 2
2
4 3
1
3
100 1 6
3
4
1001 7 1007 5
3
8 11 6
2
2 9
    Output
    5
1
19

    1. Test 1

      Chiến lược tối ưu là chọn một mảng làm "nơi chứa" nhận phần tử nhỏ nhất bị chuyển đi từ các mảng khác, còn các mảng khác sau khi chuyển đi phần tử nhỏ nhất của chính nó thì độ đẹp mới của chúng là phần tử nhỏ nhì (second-min). Test 1: n=2, mảng1=[1,2], mảng2=[4,3]. Chuyển phần tử nhỏ nhất của mảng2 (giá trị 3) sang mảng1: mảng2 chỉ còn [4] nên min mới là 4, còn mảng1 vẫn giữ min=1 vì 1 vốn đã là giá trị nhỏ nhất toàn cục. Tổng độ đẹp = 1+4 = 5, khớp sampleOutput.

    2. Test 2

      n=1 chỉ có một mảng [100,1,6], không có mảng khác để chuyển phần tử đến nên độ đẹp giữ nguyên bằng min(100,1,6) = 1.

  • Rating 1200

    Sort(mở Codeforces trong tab mới)

    Cho hai chuỗi a, b độ dài n và q truy vấn (l, r) độc lập. Mỗi thao tác đổi một ký tự a_i thành ký tự bất kỳ. Tìm số thao tác ít nhất để đoạn a[l..r] sau khi sắp xếp bằng đoạn b[l..r] sau khi sắp xếp.

    Test mẫu & giải thích
    Input
    3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6
    Output
    0
1
0
2
2
1
1
0

    1. Test 1

      Ở test đầu tiên (n=5, a="abcde", b="edcba"), truy vấn (1,5) lấy cả hai chuỗi: sắp xếp a[1..5] và b[1..5] đều ra "abcde", nên không cần đổi ký tự nào — đáp án 0.

    2. Test 2

      Truy vấn (1,4): a[1..4]="abcd" sau khi sắp xếp là "abcd", còn b[1..4]="edcb" sau khi sắp xếp là "bcde". Đổi ký tự 'a' của a thành 'e' thì đoạn a thành "ebcd", sắp xếp ra "bcde" trùng với b — chỉ 1 thao tác, đáp án 1.