Selection sort là gì? Thuật toán sắp xếp chọn Selection sort trong C/C++

Rate this post

Selection sort được dùng khá phổ biến trong ngôn ngữ lập trình C/C++. Bài viết này Gockhampha.edu.vn.COM.VN sẽ giúp bạn hiểu rõ hơn về Selection sort một cách đơn giản và dễ hiểu nhất nhé

Bạn đang đọc: Selection sort là gì? Thuật toán sắp xếp chọn Selection sort trong C/C++

Contents

1 Sắp xếp chọn – Selection sort là gì?
2 Thuật toán sắp xếp chọn Selection sort
- 2.1 Code minh họa
- 2.2 Gợi ý:

Sắp xếp chọn – Selection sort là gì?

Khái niệm

Selection sort còn được gọi là thuật toán sắp xếp chọn. Thuật toán này sẽ giúp so sánh các phần tử trong mảng với nhau để tìm các phần tử có giá trị nhỏ nhất hoặc lớn nhất (tùy theo thứ tự sắp xếp). Sau đó đẩy các giá trị ấy về phía đầu của mảng để tạo thành một dãy số sắp xếp theo thứ tự hoàn chỉnh.

Ví dụ thuật toán sắp xếp chọn – Selection Sort

Ý tưởng

Ý tưởng thuật toán sắp xếp chọn dưới đây sẽ sắp xếp mảng theo thứ tự từ bé đến lớn (tăng dần). Bạn có thể thực hiện tương tự cho trường hợp sắp xếp từ lớn đến bé (giảm dần).

Với thuật toán sắp xếp, ta chia mảng thành các phần sau:

Phần đã được sắp xếp sẽ nằm bên trái
Phần chưa được sắp xếp sẽ nằm bên phải. Lúc mới bắt đầu thì các phần tử trong danh sách sẽ nằm bên phải do chưa được sắp xếp.

Quá trình sắp xếp diễn ra như sau:

Quét toàn bộ các giá trị trong phần chưa được sắp xếp để tìm ra phần tử bé nhất.
Đưa phần tử đó lên vị trí đầu tiên.
Tiếp theo, phần tử nhỏ thứ hai vào vị trí kế bên phần tử nhỏ nhất. Lặp lại quá trình này cho đến khi phần tử lớn nhất đặt vào vị trí cuối cùng.

Ý tưởng thuật toán sắp xếp chọn – Selection Sort

Giải thuật

Bước 1: Chạy vòng lặp for (i = 0; i

Bước 2: Chạy vòng lặp for (j = i+1; j

Bước 3: Hoán vị a[min] và a[i].

Bước 4: Liên tục lặp lại 3 bước trên cho đến khi sắp xếp dãy theo thứ tự đúng thì ngừng.

Tìm hiểu thêm: Cap là gì? Ý nghĩa của cap, cách sử dụng từ cap trên MXH chuẩn

Giải thuật sắp xếp chọn – Selection Sort

Thuật toán sắp xếp chọn Selection sort

Code minh họa

Code: Thuật toán sắp xếp chọn selection sort

Gợi ý:

Gán giá trị 0 cho a[min].
Tạo vòng lặp for cho các phần tử bên trái và bên phải trong danh sách.
Tìm và sắp xếp phần tử nhỏ nhất.
Sau khi tìm được phần tử nhỏ nhất thì đổi chỗ phần tử đó với phần tử đầu tiên.
Lặp lại cho tới khi các phần tử trong danh sách được sắp xếp xong.

>>>>>Xem thêm: CPM là gì? Ưu nhược điểm của quảng cáo CPM trong Digital Marketing

Input và Output

Hy vọng bài viết này sẽ giúp bạn làm chủ được Selection sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công!

Thuật Ngữ