Basic Sorting Algorithms (Day 32) | FE Master

🎯 Tại sao phải học Sắp xếp?

Sắp xếp (Sorting) là bài toán vỡ lòng nhưng chứa đựng tư duy tối ưu thuật toán. Có hàng chục cách để sắp xếp 1 bộ bài, máy tính cũng vậy.

Chúng ta sẽ đi sâu vào 3 thuật toán "rùa bò" (Chậm nhưng dễ hiểu): Bubble Sort, Selection Sort, Insertion Sort. Độ phức tạp trung bình của chúng đều là O(N²).

1. Bubble Sort (Sắp xếp Nổi bọt)

Tư duy: "Thấy thằng nào đứng sai chỗ thì đổi ngay". Giống như bong bóng nhẹ sẽ nổi lên mặt nước, phần tử lớn nhất sẽ "nổi" dần về cuối mảng sau mỗi vòng lặp.

Quy trình: So sánh 2 số liền kề. Nếu số trước > số sau thì đổi chỗ (Swap).

Minh họa chạy tay: Mảng [5, 1, 4, 2, 8]

Lần 1 (Đưa số lớn nhất về cuối):

[5, 1, 4, 2, 8] -> 5 > 1 -> Đổi -> [1, 5, 4, 2, 8]
[1, 5, 4, 2, 8] -> 5 > 4 -> Đổi -> [1, 4, 5, 2, 8]
[1, 4, 5, 2, 8] -> 5 > 2 -> Đổi -> [1, 4, 2, 5, 8]
[1, 4, 2, 5, 8] -> 5 < 8 -> Giữ -> [1, 4, 2, 5, 8]

👉 Kết thúc Lần 1: Số 8 đã nằm đúng chỗ cuối cùng. (Chúng ta không cần xét nó nữa).

graph LR A[5, 1, 4, 2, 8] -- 1. Swap 5-1 --> B[1, 5, 4, 2, 8] B -- 2. Swap 5-4 --> C[1, 4, 5, 2, 8] C -- 3. Swap 5-2 --> D[1, 4, 2, 5, 8] D -- 4. 5 < 8 OK --> E[1, 4, 2, 5, 8] style E stroke:#f00,stroke-width:2px

Lần 2 (Xét [1, 4, 2, 5]):

[1, 4, 2, 5, 8] -> 1 < 4 -> Giữ.
[1, 4, 2, 5, 8] -> 4 > 2 -> Đổi -> [1, 2, 4, 5, 8]
[1, 2, 4, 5, 8] -> 4 < 5 -> Giữ.

👉 Kết thúc Lần 2: Số 5, 8 đã xong. Mảng lúc này [1, 2, 4, 5, 8] thực ra đã xong rồi.

2. Selection Sort (Sắp xếp Chọn)

Tư duy: "Quét một lượt, chọn thằng bé nhất (Min), lôi cổ nó về đầu".

Khác với Bubble Sort (đổi chỗ liên tục), Selection Sort chỉ đổi chỗ 1 lần duy nhất sau mỗi vòng quét. -> Ít thao tác Swap hơn.

Minh họa chạy tay: Mảng [29, 10, 14, 37, 13]

Vòng 1: Tìm Min trong toàn bộ mảng. Thấy 10 là Min.
-> Đổi chỗ 10 với phần tử đầu tiên (29).
-> Mảng: [10, 29, 14, 37, 13]. (10 đã yên vị).
Vòng 2: Tìm Min trong phần còn lại [29, 14, 37, 13]. Thấy 13 là Min.
-> Đổi chỗ 13 với phần tử đầu (của phần còn lại) là 29.
-> Mảng: [10, 13, 14, 37, 29]. (10, 13 đã yên vị).
Vòng 3: Tìm Min trong [14, 37, 29]. Thấy 14. Nó đang ở đúng chỗ rồi. Khỏi đổi.
-> Mảng: [10, 13, 14, 37, 29].
... cứ thế tiếp tục.

3. Insertion Sort (Sắp xếp Chèn)

Tư duy: "Xếp bài tây". Tay trái cầm những lá bài đã xếp ngon lành. Tay phải bốc lá bài mới và nhét nó vào khe thích hợp trên tay trái.

Đặc điểm Vàng: Cực kỳ nhanh nếu mảng đầu vào đã gần được sắp xếp (Best case O(N)). Bubble và Selection thì ngu ngơ hơn, kể cả đã sắp xếp rồi chúng vẫn cặm cụi chạy O(N²).

Câu hỏi FE:

Dãy số: [2, 3, 5, 1, 9]. Khi dùng Insertion Sort, tại bước chèn số 1, chuyện gì sẽ xảy ra?

Trả lời:

Tay trái đang cầm: [2, 3, 5].
Bốc số 1 lên.
So 1 với 5 -> nhỏ hơn -> Dịch 5 sang phải.
So 1 với 3 -> nhỏ hơn -> Dịch 3 sang phải.
So 1 với 2 -> nhỏ hơn -> Dịch 2 sang phải.
Hết chỗ so -> Chèn 1 vào đầu.
Kết quả: [1, 2, 3, 5, 9].

🎯 Tại sao phải học Sắp xếp?

Sắp xếp (Sorting) là bài toán vỡ lòng nhưng chứa đựng tư duy tối ưu thuật toán. Có hàng chục cách để sắp xếp 1 bộ bài, máy tính cũng vậy.

Chúng ta sẽ đi sâu vào 3 thuật toán "rùa bò" (Chậm nhưng dễ hiểu): Bubble Sort, Selection Sort, Insertion Sort. Độ phức tạp trung bình của chúng đều là O(N²).

1. Bubble Sort (Sắp xếp Nổi bọt)

Quy trình: So sánh 2 số liền kề. Nếu số trước > số sau thì đổi chỗ (Swap).

Minh họa chạy tay: Mảng [5, 1, 4, 2, 8]

Lần 1 (Đưa số lớn nhất về cuối):

[5, 1, 4, 2, 8] -> 5 > 1 -> Đổi -> [1, 5, 4, 2, 8]
[1, 5, 4, 2, 8] -> 5 > 4 -> Đổi -> [1, 4, 5, 2, 8]
[1, 4, 5, 2, 8] -> 5 > 2 -> Đổi -> [1, 4, 2, 5, 8]
[1, 4, 2, 5, 8] -> 5 < 8 -> Giữ -> [1, 4, 2, 5, 8]

👉 Kết thúc Lần 1: Số 8 đã nằm đúng chỗ cuối cùng. (Chúng ta không cần xét nó nữa).

Lần 2 (Xét [1, 4, 2, 5]):

[1, 4, 2, 5, 8] -> 1 < 4 -> Giữ.
[1, 4, 2, 5, 8] -> 4 > 2 -> Đổi -> [1, 2, 4, 5, 8]
[1, 2, 4, 5, 8] -> 4 < 5 -> Giữ.

👉 Kết thúc Lần 2: Số 5, 8 đã xong. Mảng lúc này [1, 2, 4, 5, 8] thực ra đã xong rồi.

2. Selection Sort (Sắp xếp Chọn)

Tư duy: "Quét một lượt, chọn thằng bé nhất (Min), lôi cổ nó về đầu".

Khác với Bubble Sort (đổi chỗ liên tục), Selection Sort chỉ đổi chỗ 1 lần duy nhất sau mỗi vòng quét. -> Ít thao tác Swap hơn.

Minh họa chạy tay: Mảng [29, 10, 14, 37, 13]

Vòng 1: Tìm Min trong toàn bộ mảng. Thấy 10 là Min.
-> Đổi chỗ 10 với phần tử đầu tiên (29).
-> Mảng: [10, 29, 14, 37, 13]. (10 đã yên vị).
Vòng 2: Tìm Min trong phần còn lại [29, 14, 37, 13]. Thấy 13 là Min.
-> Đổi chỗ 13 với phần tử đầu (của phần còn lại) là 29.
-> Mảng: [10, 13, 14, 37, 29]. (10, 13 đã yên vị).
Vòng 3: Tìm Min trong [14, 37, 29]. Thấy 14. Nó đang ở đúng chỗ rồi. Khỏi đổi.
-> Mảng: [10, 13, 14, 37, 29].
... cứ thế tiếp tục.

3. Insertion Sort (Sắp xếp Chèn)

Tư duy: "Xếp bài tây". Tay trái cầm những lá bài đã xếp ngon lành. Tay phải bốc lá bài mới và nhét nó vào khe thích hợp trên tay trái.

Câu hỏi FE:

Dãy số: [2, 3, 5, 1, 9]. Khi dùng Insertion Sort, tại bước chèn số 1, chuyện gì sẽ xảy ra?

Trả lời:

Tay trái đang cầm: [2, 3, 5].
Bốc số 1 lên.
So 1 với 5 -> nhỏ hơn -> Dịch 5 sang phải.
So 1 với 3 -> nhỏ hơn -> Dịch 3 sang phải.
So 1 với 2 -> nhỏ hơn -> Dịch 2 sang phải.
Hết chỗ so -> Chèn 1 vào đầu.
Kết quả: [1, 2, 3, 5, 9].

Thuật toán Sắp xếp Cơ bản (Basic Sorting)

lesson.content.title

🎯 Tại sao phải học Sắp xếp?

1. Bubble Sort (Sắp xếp Nổi bọt)

Minh họa chạy tay: Mảng [5, 1, 4, 2, 8]

2. Selection Sort (Sắp xếp Chọn)

Minh họa chạy tay: Mảng [29, 10, 14, 37, 13]

3. Insertion Sort (Sắp xếp Chèn)

Câu hỏi FE:

Thuật toán Sắp xếp Cơ bản (Basic Sorting)

lesson.content.title

🎯 Tại sao phải học Sắp xếp?

1. Bubble Sort (Sắp xếp Nổi bọt)

Minh họa chạy tay: Mảng [5, 1, 4, 2, 8]

2. Selection Sort (Sắp xếp Chọn)

Minh họa chạy tay: Mảng [29, 10, 14, 37, 13]

3. Insertion Sort (Sắp xếp Chèn)

Câu hỏi FE: