Mục lục
Thuật toán Insertion Sort là gì? Giải thích dễ hiểu kèm demo trực quan
Insertion Sort là một trong những thuật toán sắp xếp đơn giản nhưng rất trực quan. Ý tưởng của nó giống như cách bạn sắp xếp bài trên tay: mỗi lần rút thêm một lá bài mới, bạn sẽ “chèn” nó vào đúng vị trí trong phần đã được sắp xếp trước đó.
Dù không phải là thuật toán tối ưu cho dữ liệu lớn, Insertion Sort lại cực kỳ hữu ích để hiểu cơ chế sắp xếp theo từng phần và hoạt động rất tốt khi dữ liệu gần như đã được sắp xếp sẵn.
Insertion Sort giải bài toán gì?
Bài toán cơ bản:
- Cho một mảng các phần tử (thường là số).
- Cần sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.
Insertion Sort xử lý dần dần từ trái sang phải, luôn giữ cho phần bên trái đang ở trạng thái đã sắp xếp, rồi chèn phần tử tiếp theo vào đúng vị trí.
Ý tưởng chính của thuật toán Insertion Sort
Thuật toán hoạt động theo các bước:
- Xem phần tử đầu tiên là một mảng con đã sắp xếp.
- Lấy phần tử tiếp theo (gọi là
key). - So sánh
keyvới các phần tử bên trái, dịch các phần tử lớn hơn sang phải. - Chèn
keyvào vị trí còn trống thích hợp. - Lặp lại cho đến khi duyệt hết mảng.
Điểm mạnh: khi mảng gần như đã được sắp xếp, Insertion Sort chạy rất nhanh.
Ví dụ minh họa
Cho mảng:
[5, 3, 8, 4, 2, 7]Một vài bước đầu:
- Bước 1: Xem [5] là đã sắp xếp.
- Bước 2: Lấy 3, so với 5 → 3 < 5 → dịch 5 sang phải → chèn 3 vào đầu → [3, 5, 8, 4, 2, 7]
- Bước 3: Lấy 8, so với 5 → 8 > 5 → giữ nguyên → [3, 5, 8, 4, 2, 7]
- Bước 4: Lấy 4, so với 8 → dịch 8, so với 5 → dịch 5, so với 3 → dừng → chèn 4 → …
Demo Insertion Sort bằng JavaScript
Demo dưới đây minh họa trực quan cách Insertion Sort hoạt động trên mảng [5, 3, 8, 4, 2, 7]:
- Tô màu phần đã sắp xếp.
- Tô màu phần tử
keyđang được chèn. - Hiển thị từng lần so sánh, dịch phần tử và chèn vào vị trí đúng.
- Log chi tiết từng bước.
Demo: Thuật toán Insertion Sort trên mảng nhỏ
Mảng hiện tại
Log từng bước
Sẵn sàng chạy thuật toán.
Kết quả cuối cùng
Chưa có kết quả.
Phân tích đoạn code Insertion Sort
1. Ghi lại các bước chạy
function insertionSortWithSteps(arr) {
var a = arr.slice();
var n = a.length;
var steps = [];
for (var i = 1; i < n; i++) {
var key = a[i];
var j = i - 1;
// Chọn key
steps.push({
type: "pick",
keyIndex: i,
keyValue: key,
sortedBoundary: i - 1,
array: a.slice()
});
while (j >= 0 && a[j] > key) {
// So sánh với phần tử ở vị trí j
steps.push({
type: "compare",
compareIndex: j,
keyValue: key,
sortedBoundary: i - 1,
array: a.slice()
});
// Dịch phần tử a[j] sang phải
a[j + 1] = a[j];
steps.push({
type: "shift",
from: j,
to: j + 1,
keyValue: key,
sortedBoundary: i - 1,
array: a.slice()
});
j--;
}
// Chèn key vào vị trí đúng
a[j + 1] = key;
steps.push({
type: "insert",
insertIndex: j + 1,
keyValue: key,
sortedBoundary: i,
array: a.slice()
});
}
return { steps: steps, sorted: a };
}2. Vẽ mảng & highlight từng phần tử
function renderInsertionArray(container, arr, options) {
container.innerHTML = "";
var sortedBoundary = options.sortedBoundary;
var keyIndex = options.keyIndex;
var compareIndex = options.compareIndex;
var insertIndex = options.insertIndex;
arr.forEach(function(value, index) {
var div = document.createElement("div");
div.className = "ins-cell";
if (sortedBoundary != null && index <= sortedBoundary) {
div.classList.add("ins-sorted");
}
if (index === compareIndex) {
div.classList.add("ins-compare");
}
if (index === keyIndex || index === insertIndex) {
div.classList.add("ins-key");
}
div.textContent = value;
container.appendChild(div);
});
}3. Chạy animation từng bước
function playInsertionSteps(steps, sortedArray) {
var index = 0;
insertionLog.innerHTML = "";
insertionResult.textContent = "Đang chạy thuật toán...";
function next() {
if (index >= steps.length) {
renderInsertionArray(insertionArray, sortedArray, {
sortedBoundary: sortedArray.length - 1
});
insertionResult.innerHTML =
"Mảng đã được sắp xếp: <strong>[" + sortedArray.join(", ") + "]</strong>";
return;
}
var step = steps[index];
var msg = "";
var options = {
sortedBoundary: step.sortedBoundary != null ? step.sortedBoundary : null,
keyIndex: null,
compareIndex: null,
insertIndex: null
};
if (step.type === "pick") {
msg =
"Chọn key = " +
step.keyValue +
" tại vị trí " +
step.keyIndex +
", phần bên trái đang được xem là đã sắp xếp.";
options.keyIndex = step.keyIndex;
} else if (step.type === "compare") {
msg =
"So sánh key = " +
step.keyValue +
" với phần tử ở vị trí " +
step.compareIndex +
" (giá trị " +
step.array[step.compareIndex] +
").";
options.compareIndex = step.compareIndex;
} else if (step.type === "shift") {
msg =
"Dịch phần tử ở vị trí " +
step.from +
" sang vị trí " +
step.to +
" để chừa chỗ cho key (key = " +
step.keyValue +
").";
} else if (step.type === "insert") {
msg =
"Chèn key = " +
step.keyValue +
" vào vị trí " +
step.insertIndex +
".";
options.insertIndex = step.insertIndex;
}
renderInsertionArray(insertionArray, step.array, options);
var p = document.createElement("p");
p.innerHTML = msg;
insertionLog.appendChild(p);
insertionLog.scrollTop = insertionLog.scrollHeight;
index++;
setTimeout(next, 600);
}
next();
}Khi nào nên dùng Insertion Sort?
- Khi mảng nhỏ, hoặc kích thước dữ liệu không quá lớn.
- Khi dữ liệu gần như đã được sắp xếp sẵn.
- Khi cần một thuật toán đơn giản, dễ cài đặt, dễ debug.
Kết luận
Insertion Sort cho bạn một góc nhìn rất thực tế về cách sắp xếp dần dần, từng phần tử một. Với demo trực quan, bạn có thể thấy rõ từng bước chọn key, so sánh, dịch phần tử và chèn vào đúng vị trí – giúp việc hiểu và ghi nhớ thuật toán trở nên dễ dàng hơn rất nhiều.
Bình luận