Cách Giải Sắp Xếp Chèn (Insertion Sort), Dể Hiểu
Sắp Xếp Chèn là một thuật toán sắp xếp đơn giản và hiệu quả cho các tập dữ liệu nhỏ hoặc gần như đã được sắp xếp. Thuật toán này bắt chước cách mà người chơi bài thường sắp xếp các quân bài của mình.
Định Nghĩa
Sắp Xếp Chèn (Insertion Sort) là một thuật toán dựa vào việc di chuyển từng phần tử vào đúng chỗ của nó trong một mảng đã sắp xếp.
Bắt đầu với phần tử đầu tiên và xem nó như là một mảng đã sắp xếp. Từ đây, ta sẽ lần lượt lấy từng phần tử tiếp theo từ phần chưa sắp xếp.
Khi lấy một phần tử mới từ phần chưa sắp xếp, ta sẽ so sánh và di chuyển nó vào đúng vị trí trong phần đã sắp xếp.
Quá trình này lặp đi lặp lại cho đến khi toàn bộ mảng được sắp xếp.
Để dể hình dung hơn, bạn có thể tạo và xem diễn họa của các thuật toán sắp xếp tại đây: https://visualgo.net/en/sorting
Bản Chất
Sắp Xếp Chèn hoạt động theo từng bước đơn giản: đầu tiên, bạn lấy phần tử đầu tiên trong mảng chưa sắp xếp. Giả sử bạn đã có một phần đã sắp xếp—lúc đầu, phần này chỉ có một phần tử. Bạn sẽ đưa phần tử đầu tiên từ phần chưa sắp xếp vào vị trí đúng trong phần đã sắp xếp.
Khi đã đặt phần tử vào vị trí đúng, bạn tiếp tục lấy phần tử tiếp theo từ phần chưa sắp xếp. Lặp lại các bước trên cho đến khi không còn phần tử nào trong phần chưa sắp xếp.
Điều này tạo ra một mảng sắp xếp dần dần. Mỗi lần di chuyển phần tử mới vào đúng vị trí sẽ khiến phần đã sắp xếp tăng lên một phần tử.
Như vậy, mảng ban đầu hỗn loạn sẽ trở thành trật tự mà không cần nhiều phép hoán đổi phức tạp.
Triển Khai
Để triển khai thuật toán Sắp Xếp Chèn trong một ngôn ngữ lập trình, ta cần:
- Một mảng chứa các giá trị cần sắp xếp.
- Một vòng lặp bên ngoài (for i) để chọn giá trị cần sắp xếp. Đối với một mảng có (n) giá trị, vòng lặp bên ngoài sẽ bỏ qua giá trị đầu tiên và chạy (n - 1) lần.
- Một vòng lặp bên trong (while) duyệt qua phần đã sắp xếp của mảng, để tìm vị trí chèn giá trị. Nếu giá trị cần sắp xếp nằm ở chỉ số (i), thì phần đã sắp xếp của mảng bắt đầu từ chỉ số (0) và kết thúc ở chỉ số (i - 1).
Mã TypeScript sẽ trông như sau:
import { expect } from 'jsr:@std/expect';
function insertionSort(nums: number[]): number[] {
// Nếu mảng có 1 phần tử hoặc rỗng, không cần sắp xếp
if (nums.length <= 1) return nums;
// Duyệt qua từng phần tử từ vị trí thứ 2 (chỉ số 1) đến cuối mảng
for (let i = 1; i < nums.length; i++) {
// Lưu lại giá trị hiện tại của phần tử đang xét
const tmp = nums[i];
// Bắt đầu so sánh phần tử hiện tại với các phần tử trước nó
let j = i - 1;
// Dịch chuyển các phần tử lớn hơn giá trị hiện tại sang phải một vị trí
while (nums[j] > tmp && j >= 0) {
nums[j + 1] = nums[j];
j--;
}
// Chèn giá trị hiện tại vào vị trí thích hợp
nums[j + 1] = tmp;
}
// Trả về mảng đã được sắp xếp
return nums;
}
Deno.test('test', () => {
const input = [3, 15, 7, 1, 12, 19, 5, 8, 2, 10];
const output = input.toSorted((a, b) => a - b);
expect(insertionSort(input)).toStrictEqual(output);
});
Big O
Độ phức tạp thời gian của Sắp Xếp Chèn thường là O(n²). Tại sao lại vậy? Bởi vì trong trường hợp xấu nhất, mỗi phần tử cần so sánh với tất cả các phần tử trước đó.
Đối với mảng đã sắp xếp, thuật toán sẽ hoạt động nhanh hơn nhiều, với độ phức tạp gần với O(n). Do vậy, Sắp Xếp Chèn hoạt động tốt khi mảng gần như đã có trật tự.
Tuy nhiên, đối với các mảng ngẫu nhiên và lớn, O(n²) khiến thuật toán này trở nên chậm. Tốc độ của nó không thể cạnh tranh với các thuật toán sắp xếp nhanh hơn như Sắp Xếp Nhanh hay Sắp Xếp Trộn.
Vì vậy, Sắp Xếp Chèn không phải là lựa chọn tối ưu cho các mảng lớn, nhưng vẫn có chỗ đứng trong các ứng dụng cụ thể.
Toàn Cảnh
Trong hệ thống các thuật toán sắp xếp, Sắp Xếp Chèn nằm ở mức đơn giản và cơ bản. Nó phù hợp cho những tình huống nhỏ và yêu cầu trực quan, khi các thuật toán phức tạp không thực sự cần thiết.
Điều này làm cho Sắp Xếp Chèn trở thành một phần của nhóm thuật toán sắp xếp “dễ hiểu,” là lựa chọn lý tưởng khi hiệu suất không phải là ưu tiên hàng đầu.
Trong các tình huống yêu cầu các thao tác nhỏ, dễ dàng theo dõi, Sắp Xếp Chèn cho phép bạn kiểm soát từng bước và thấy rõ từng sự thay đổi trong mảng.
Do đó, trong một bức tranh lớn hơn, Sắp Xếp Chèn là một công cụ dễ học, dễ nhớ và thực sự hiệu quả trong những trường hợp nhất định.
Ứng Dụng
Sắp Xếp Chèn thường được dùng trong việc sắp xếp các dữ liệu nhỏ hoặc các danh sách mà đã gần sắp xếp. Ví dụ, khi sắp xếp các bài kiểm tra theo thứ tự điểm, nếu danh sách chỉ có vài bài và gần như đã xếp sẵn, Sắp Xếp Chèn hoạt động rất tốt.
Một ứng dụng khác là trong việc xếp thứ tự dữ liệu khi nhập liệu. Nếu bạn cần thêm từng mục vào danh sách có thứ tự, Sắp Xếp Chèn là lựa chọn hiệu quả.
Đối với lập trình viên, Sắp Xếp Chèn cũng hữu ích khi cần sắp xếp các dữ liệu nhỏ trong bộ nhớ cache mà không cần các thuật toán phức tạp.
Cuối cùng, Sắp Xếp Chèn là một công cụ lý tưởng khi không gian và bộ nhớ bị hạn chế, bởi vì nó thực hiện sắp xếp trực tiếp trên mảng mà không cần nhiều bộ nhớ bổ sung.
Hiểu Lầm
Một hiểu lầm phổ biến là cho rằng Sắp Xếp Chèn nhanh như Sắp Xếp Nhanh. Thực tế, chúng khác nhau; Sắp Xếp Chèn có thể chậm hơn rất nhiều đối với mảng lớn.
Ngoài ra, Sắp Xếp Chèn không hiệu quả khi xử lý dữ liệu ngẫu nhiên hoặc dữ liệu có kích thước lớn. Trong các trường hợp đó, các thuật toán khác có độ phức tạp O(n log n) thường sẽ vượt trội.
Sắp Xếp Chèn đôi khi bị nhầm là một cách tối ưu cho mọi trường hợp, nhưng thực ra nó chỉ mạnh ở các mảng nhỏ và gần như đã sắp xếp.
Cuối cùng, không nên coi Sắp Xếp Chèn là giải pháp toàn năng; thay vào đó, hãy dùng nó khi phù hợp để tận dụng sức mạnh thực sự của nó.
Tóm Tắt
Sắp Xếp Chèn giúp bạn sắp xếp dữ liệu một cách trực quan, lần lượt chèn từng phần tử vào vị trí đúng của nó.
Thuật toán này dễ hiểu và dễ triển khai, nhưng hiệu suất không cao đối với các mảng lớn hoặc ngẫu nhiên. Nó phù hợp hơn khi mảng đã gần xếp sẵn.
Nếu bạn cần sắp xếp dữ liệu trong bộ nhớ cache hay các dữ liệu nhỏ, Sắp Xếp Chèn là lựa chọn hợp lý.
Nhớ rằng mỗi thuật toán có vị trí của nó; Sắp Xếp Chèn là một công cụ hữu ích khi biết cách áp dụng đúng lúc, đúng chỗ.