Thuật toán Sắp xếp xếp chọn - Mô phòng bằng C#

1. Bài toán sắp xếp chọn

Trong quá trình thao tác dữ liệu, sẽ có những trường hợp cần phải sắp xếp dữ liệu trong danh sách theo một thứ tự nào đó theo các yêu cầu. Tùy từng loại cấu trúc dữ liệu khác nhau sẽ có phương án sắp xếp tối ưu cho cấu trúc dữ liệu đó. Xét giới hạn trong kiểu dữ liệu danh sách đơn giản là mảng các phần tử, Sắp xếp chọn – Selection Sort là một kiểu sắp xếp đơn giản nhất, thuật toán rõ ràng, dễ hiểu.

Tư tưởng của của thuật toán này như sau: Sẽ có n – 1 vòng lặp duyệt qua danh sách (n là tổng số phần tử), tại mỗi vòng lặp sẽ chọn phần tử nhỏ nhất đưa lên đầu danh sách. Như vậy sau vòng lặp thứ nhất thu được phần tử nhỏ nhất tại vị trí đầu tiên, sau vòng lặp thứ 2 thu được phần tử nhỏ nhất trong danh sách còn lại (không tính phần tử thứ 2) tại vị trí thứ hai… cứ như vậy cho đến vòng lặp thứ n – 1 sẽ còn 2 phần tử, ta lấy phần tử nhỏ hơn đưa vào vị trí thứ n – 1 và tất nhiên vị trí cuối cùng sẽ là phần tử lớn nhất. Tại mỗi vòng lặp để xác định phần tử có giá trị nhỏ nhất ta cần dùng thêm một vòng lặp bên trong, như vậy sẽ có 2 vòng lặp lồng nhau. Ta nhận thấy rằng, đối với vòng lặp ngoài, khi đến lượt lặp lại thứ 2 thì phần tử đầu tiên sẽ không còn giá trị vì nó đã được đưa vào đúng vị trí, tương tự đến lần lặp thứ 3 thì 2 phần tử đầu tiên không còn giá trị, hay nói cách khác chúng là mảng có tính thứ tự đã được sắp xếp. Cứ như vậy đến lần lặp n – 1 thì n – 2 phần tử đầu tiên sẽ không còn giá trị. Ý nghĩa của việc này nhằm thu hẹp “quãng đường” của vòng lặp bên trong, nhằm tối ưu chi phí.

2. Cài đặt bài toán với mã nguồn Csharp
Chương trình được tổ chức trong class SelectionSort, thuộc tính của class là một mảng số nguyên. Ở phương thức khởi tạo (Constructure) sẽ đưa vào số lượng phần tử của mảng, sau đó gọi tới phương thức createRandom() để khởi tạo ngẫu nhiên giá trị cho mảng. Phương thức show() để xuất các phần tử của mảng ra màn hình. Cốt lõi của class nằm ở phương thức sort()

Trong phương thức sort ta thấy đầu tiên sẽ khởi tạo 2 biến: Min và temp. temp là biến tạm còn Min dùng để lưu giá trị nhỏ nhất ở mỗi vòng lặp. Ta thấy có 2 vòng lặp lồng nhau: Vòng lặp ngoài chạy từ 0 -> array.Length-1 (array.Length là số lượng phần tử của mảng) Vòng lặp bên trong sẽ có số bước lặp giảm dần theo vòng ngoài. Tại đầu mỗi bước của vòng lặp ngoài sẽ xác định phần tử thứ i là phần tử nhỏ nhất (tạm thời) tiếp đó trong vòng lặp trong sẽ tìm xem có phần tử nào có giá trị nhỏ hơn hay không. Mỗi lần kết thúc vòng lặp trong sẽ thu được 1 phần tử nhỏ nhất. Cứ như vậy cho đến khi hết danh sách.