Cách Giải Sắp Xếp Chọn (Selection Sort), Dể Hiểu
Sắp Xếp Chọn là một thuật toán sắp xếp đơn giản, được phát minh vào những năm đầu của thế kỷ 20. Thuật toán này hoạt động dựa trên nguyên lý tìm kiếm phần tử nhỏ nhất trong một dãy số và đưa nó về vị trí đầu tiên, sau đó lặp lại quá trình cho các phần tử còn lại.
Định Nghĩa
Thuật toán Sắp Xếp Chọn (Selection Sort) là một trong những thuật toán sắp xếp cơ bản. Để bắt đầu, bạn hãy hình dung: mỗi khi bạn duyệt qua một mảng, bạn sẽ tìm ra giá trị nhỏ nhất. Giá trị này sẽ được đẩy lên đầu mảng để làm bước đầu tiên trong quá trình sắp xếp.
Nói cách khác, ở mỗi vòng lặp của thuật toán, bạn chọn phần tử nhỏ nhất trong phần chưa được sắp xếp của mảng. Phần tử nhỏ nhất này được di chuyển vào vị trí phù hợp, ngay ở đầu phần chưa được sắp xếp.
Thuật toán cứ thế tiếp tục cho đến khi tất cả phần tử trong mảng được sắp xếp. Khi đó, phần chưa sắp xếp ngày càng nhỏ dần, và dần dần bạn có được một mảng sắp xếp tăng dần.
Điều này có vẻ đơn giản, nhưng hãy thử suy ngẫm: Sắp Xếp Chọn không hề nhanh trong các trường hợp dữ liệu lớn, nhưng nó lại rất hiệu quả và dễ hiểu với những tập dữ liệu nhỏ.
Để dể hình dung hơn, bạn có thể 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
Vậy thuật toán Sắp Xếp Chọn hoạt động như thế nào? Đầu tiên, bạn sẽ duyệt qua toàn bộ mảng để tìm phần tử có giá trị nhỏ nhất. Phần tử này được đổi chỗ với phần tử ở đầu mảng.
Sau khi phần tử đầu tiên đã được đặt đúng chỗ, bạn chuyển sang phần tử kế tiếp, duyệt lại phần còn lại của mảng để tìm giá trị nhỏ nhất trong đó.
Tiếp tục quá trình này, bạn cứ tìm phần tử nhỏ nhất và đặt nó vào vị trí tiếp theo trong mảng. Lặp lại cho đến khi bạn hoàn tất việc sắp xếp toàn bộ mảng.
Nhờ vậy, mỗi vòng lặp đảm bảo ít nhất một phần tử được đặt vào đúng vị trí của nó, giúp từng bước làm mảng có trật tự hơn.
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, chúng 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 trong (for j) để duyệt qua mảng, tìm giá trị nhỏ nhất và di chuyển nó lên đầu mảng. Vòng lặp này sẽ duyệt qua một phần tử ít hơn mỗi lần nó chạy.
- Một vòng lặp bên ngoài (for i) để kiểm soát số lần vòng lặp bên trong phải chạy. Với một mảng có n phần tử, vòng lặp bên ngoài cần chạy n-1 lần.
Mã lệnh TypeScript sẽ trông như sau:
import { expect } from 'jsr:@std/expect';
function selectionSort(nums: number[]): number[] {
// Nếu mảng có 1 phần tử hoặc rỗng thì không cần sắp xếp, trả về mảng ban đầu
if (nums.length <= 1) return nums;
// Duyệt qua từng phần tử trong mảng
for (let i = 0; i < nums.length; i++) {
// Giả định phần tử tại vị trí i là nhỏ nhất
let minIndex = i;
// Tìm phần tử nhỏ nhất trong mảng từ vị trí i+1 đến cuối mảng
for (let j = i + 1; j < nums.length; j++) {
// Nếu tìm thấy phần tử nhỏ hơn, cập nhật minIndex
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// Nếu phần tử nhỏ nhất tìm thấy không phải là phần tử tại vị trí i, thực hiện đổi chỗ
if (i !== minIndex) {
[nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
}
}
// 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(selectionSort(input)).toStrictEqual(output);
});
Big O
Sắp Xếp Chọn có độ phức tạp thời gian là O(n²). Vì sao lại như vậy? Mỗi lần tìm phần tử nhỏ nhất, thuật toán phải duyệt qua toàn bộ phần chưa sắp xếp của mảng. Điều này tương đương với việc thực hiện phép so sánh n lần trong một mảng có n phần tử.
Trong trường hợp xấu nhất, bạn phải lặp lại việc so sánh này cho từng phần tử, dẫn đến số lần so sánh tăng theo n². Với mảng nhỏ, điều này không gây nhiều ảnh hưởng, nhưng khi mảng lớn, thời gian thực thi tăng đáng kể.
Thuật toán không thực sự tối ưu cho các ứng dụng yêu cầu tốc độ cao với dữ liệu lớn. Tuy nhiên, Sắp Xếp Chọn vẫn có ưu điểm khi bạn muốn thuật toán đơn giản và dễ hiểu.
Dù vậy, hiệu suất của Sắp Xếp Chọn trong thực tế kém hơn so với các thuật toán phức tạp hơn như Sắp Xếp Nhanh hay Sắp Xếp Trộn, đặc biệt là với các mảng lớn.
Toàn Cảnh
Sắp Xếp Chọn thuộc về nhóm thuật toán sắp xếp đơn giản và trực quan. Mặc dù độ phức tạp thời gian O(n²) không phải là lý tưởng, nhưng tính dễ hiểu và dễ triển khai giúp nó vẫn giữ vai trò quan trọng trong giáo dục và trong các trường hợp sử dụng nhỏ.
Nó cũng đóng vai trò làm nền tảng để bạn hiểu các khái niệm sắp xếp nâng cao hơn. Hiểu rõ bản chất của thuật toán này sẽ giúp bạn dễ dàng phân biệt và so sánh với các thuật toán phức tạp hơn.
Về mặt thực tế, bạn có thể không sử dụng Sắp Xếp Chọn nhiều trong các dự án lớn, nhưng nó vẫn hữu ích trong các công việc cần sắp xếp nhỏ hoặc các bài kiểm tra thuật toán.
Cuối cùng, dù không phải là lựa chọn tối ưu cho mọi tình huống, nhưng Sắp Xếp Chọn vẫn có giá trị trong việc phát triển tư duy thuật toán.
Ứng Dụng
Sắp Xếp Chọn phù hợp cho các tập dữ liệu nhỏ hoặc khi bạn cần một thuật toán đơn giản để sắp xếp nhanh. Ví dụ, khi bạn có một danh sách nhỏ cần sắp xếp trong bộ nhớ, Sắp Xếp Chọn hoàn toàn đáp ứng được.
Nó cũng hữu ích khi dạy và học thuật toán. Thông qua Sắp Xếp Chọn, bạn hiểu rõ hơn cách sắp xếp hoạt động và có thể áp dụng kiến thức này vào các thuật toán phức tạp hơn.
Trong các ứng dụng thực tế, Sắp Xếp Chọn thường không phải lựa chọn đầu tiên cho các tập dữ liệu lớn. Nhưng trong những môi trường dư dả về tài nguyên, hoặc khi hiệu suất không phải ưu tiên hàng đầu, nó vẫn là một lựa chọn phù hợp.
Với việc thực thi dễ dàng trong nhiều ngôn ngữ lập trình, Sắp Xếp Chọn cũng đóng vai trò làm bài tập cơ bản cho người học lập trình.
Hiểu Lầm
Một hiểu lầm phổ biến là nghĩ rằng Sắp Xếp Chọn có thể so sánh được về mặt hiệu suất với các thuật toán sắp xếp tiên tiến. Tuy nhiên, với độ phức tạp O(n²), thuật toán này không thích hợp cho dữ liệu lớn.
Một hạn chế khác là Sắp Xếp Chọn không có tính ổn định, tức là thứ tự của các phần tử có cùng giá trị có thể bị thay đổi sau khi sắp xếp.
Ngoài ra, nhiều người mới học có thể lầm tưởng rằng Sắp Xếp Chọn có thể tối ưu bằng cách giảm bớt số lần duyệt, nhưng điều này thường không cải thiện đáng kể hiệu suất.
Cuối cùng, cần nhớ rằng Sắp Xếp Chọn là thuật toán sắp xếp cơ bản, và không thể cạnh tranh được với các thuật toán như Sắp Xếp Nhanh hay Sắp Xếp Trộn về tốc độ.
Tóm Tắt
Hiểu rõ thuật toán Sắp Xếp Chọn giúp bạn xây dựng nền tảng kiến thức về thuật toán sắp xếp. Đây là một công cụ hữu ích trong các trường hợp đơn giản.
Dù hiệu suất không cao, nhưng nhờ tính đơn giản và trực quan, nó phù hợp cho việc học và hiểu rõ cách các thuật toán sắp xếp cơ bản vận hành.
Sắp Xếp Chọn giúp bạn phát triển tư duy lập trình, đặc biệt là trong việc quản lý mảng và hiểu sâu hơn về độ phức tạp thuật toán.
Cuối cùng, hãy nhớ rằng mỗi thuật toán đều có thế mạnh riêng. Trong trường hợp này, Sắp Xếp Chọn là một điểm bắt đầu để bạn hiểu sâu hơn về thế giới thuật toán.