Trong bài này mình sẽ giới thiệu tới những bạn thuật toán sắp xếp chọn (Selection Sort). Đây là một trong những thuật toán sắp xếp cơ bản trong C++.
Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp chọn là gì. Cách triển khai thuật toán trong C++ và ví dụ cụ thể vận dụng thuật toán để những bạn hiểu rõ hơn.
1. Sắp xếp chọn là gì?
Sắp xếp chọn là một trong những thuật toán đơn thuần. Nó thực hiện công việc so sánh những phần tử trong danh sách.
Danh sách chứa những phần tử sẽ được chia làm hai phần. Phần ở bên trái là phần được sắp xếp (sort list) và phần ở bên phải là phần chưa được sắp xếp (unsorted list).
Bài viết này được đăng tại [free tuts .net]
Ban sơ chưa được sắp xếp thì phần sorted list sẽ trống và phần unsorted list sẽ chứa tất cả những phần tử ban sơ.
Phần tử nhỏ nhất trong list sẽ được chọn và tráo đổi với vị trí trước nhất trong list, tiếp tới sẽ là vị trí nhỏ thứ hai tiếp tục được tráo đổi ngay sau vị trí nhỏ nhất.
Ví dụ minh họa:
Như những bạn thấy ở hình trên. Ở Step1, list ban sơ là 7 5 4 2. Trong list, số Hai là nhỏ nhất vì vậy chọn số Hai vào sorted list và thay thế vị trí số 7. Tương tự phần sorted list đã với số Hai và phần unsorted list còn lại 3 số là 5 4 7.
Ở Step2, chúng ta khởi đầu tìm số nhỏ thứ hai trong list đó là số 4. Tiếp tục chọn số 4 vào sorted list ở vị trí ngay sau số Hai là số nhỏ nhất. Trong sorted list hiện nay với hai số là Hai 5 và unsorted list còn lại hai số là 5 7.
Cứ tương tự Step3 và Step4 sẽ tìm số nhỏ tiếp theo trong list và chọn vào sorted list, cho tới lúc những phần tử trong list đã sắp xếp xong.
Thuật toán sắp xếp chọn (Selection Sort) trong C++.
Trong phần này mình sẽ đưa ra những bước để viết thuật toán, sau đó sẽ để thuật toán mình đã viết cho những bạn dễ hình dung.
Giảng giải thuật toán
Thiết lập trị giá nhỏ nhất (min) về vị trí số 0.
Tạo vòng lặp for để di chuyển ranh giới của sorted list và unsorted list.
Tìm phần tử nhỏ nhất trong list chưa được sắp xếp.
Sau lúc tìm được phần tử nhỏ nhất thì đổi chỗ phần tử đó với phần tử trước nhất. Ở bước này chúng ta cần viết một hàm
Swap(), hàm này mình sẽ viết ở bên dưới.Lặp lại cho tới lúc list được sắp xếp xong.
Thuật toán sắp xếp chọn
Hàm swap():
Ví dụ sắp xếp chọn trong mảng
Trong phần ví dụ sắp xếp chọn này, chúng ta sẽ thực hiện một bài toán đơn thuần đó là:
- Tạo mảng gồm những phần tử được nhập từ bàn phím.
- Tiến hành sắp xếp những phần tử sử dụng phương pháp sắp xếp chọn.
- Hiển thị mảng đã sắp xếp ra màn hình.
Gợi ý:
- Việc trước nhất sẽ viết hàm
swap()để thực hiện công việc tráo đổi vị trí lúc tìm được phần tử nhỏ nhất trong mảng. - Tiếp tới viết hàm
selectionSort()để thực hiện công việc sắp xếp những phần tử trong mảng. - Viết hàm
printSort()để in mảng đã được sắp xếp. - Tạo mảng gồm những phần tử được nhập từ bàn phím trong hàm
main(). Gọi hàmselectionSort()để sắp xếp. - Cuối cùng gọi hàm
printSort()để in mảng ra màn hình.
Code mẫu:
Kết quả:
Tương tự là chúng ta đã thực hiện xong chương trình sắp xếp mảng bằng phương pháp sắp xếp chọn. Cũng như kết thúc hướng dẫn thuật toán sắp xếp chon (Selection Sort) trong C++. Chúc những bạn thực hiện thành công!!!