Trong bài này mình sẽ giới thiệu đến 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++.

Bạn Đang Xem: Thuật toán sắp xếp chọn (Selection Sort)

Tất 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 để các bạn nắm vững 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 giản. Nó thực hiện công việc so sánh các thành phần trong list.

List chứa các thành phần sẽ tiến hành 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 không được sắp xếp (unsorted list).

Nội dung bài viết này được đăng tại [free tuts .net]

Thuở đầu không đượ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 thành phần lúc đầu.

Xem Thêm : Laravel & Pusher: Tạo một ứng dụng web thời gian thực

Thành phần nhỏ nhất trong list sẽ tiến hành chọn và tráo đổi với vị trí trước hết trong list, tiếp đến 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ư các bạn thấy ở hình trên. Ở Step1, list lúc đầu là 7 5 4 2. Trong list, số 2 là nhỏ nhất vì vậy chọn số 2 vào sorted list và thay thế vị trí số 7. Như vậy phần sorted list đã có số 2 và phần unsorted list sót lại 3 số là 5 4 7.

Ở Step2, tất cả chúng ta mở màn 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ố 2 là số nhỏ nhất. Trong sorted list giờ đây có hai số là 2 5 và unsorted list sót lại hai số là 5 7.

Cứ như vậy Step3 và Step4 sẽ tìm số nhỏ tiếp theo trong list và chọn vào sorted list, cho đến lúc các thành phần 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 các bước để viết thuật toán, sau này sẽ để thuật toán tôi đã viết cho những bạn dễ hình dung.

Giảng giải thuật toán

1. Thiết lập giá trị nhỏ nhất (min) về vị trí số 0.

2. Tạo vòng lặp for để vận chuyển ranh giới của sorted list và unsorted list.

3. Xem Thêm : Hợp chất hữu cơ là gì? Khái niệm về hợp chất hữu cơ và hóa học hữu cơ

   Tìm thành phần nhỏ nhất trong list không được sắp xếp.

4. Sau lúc tìm được thành phần nhỏ nhất thì đổi chỗ thành phần đó với thành phần trước hết. Ở bước này tất cả chúng ta cần viết một hàm Swap(), hàm này mình sẽ viết ở phía dưới.

5. Tái diễn cho tới khi 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, tất cả chúng ta sẽ thực hiện một bài toán đơn giản đó là:

• Tạo mảng gồm các thành phần được nhập từ bàn phím.
• Tiến hành sắp xếp các thành phần 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 hiển thị.

Gợi ý:

• Việc trước hết sẽ viết hàm swap() để thực hiện công việc tráo đổi vị trí khi tìm được thành phần nhỏ nhất trong mảng.
• Tiếp đến viết hàm selectionSort() để thực hiện công việc sắp xếp các thành phần trong mảng.
• Viết hàm printSort() để in mảng đã được sắp xếp.
• Tạo mảng gồm các thành phần được nhập từ bàn phím trong hàm main(). Gọi hàm selectionSort() để sắp xếp.
• Cuối cùng gọi hàm printSort() để in mảng ra màn hình hiển thị.

Code mẫu:

Kết quả:

Như vậy là tất cả chúng ta đã thực hiện xong Khóa học 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 các bạn thực hiện thành công!!!