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 DINHNGHIA.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é
Nội dung bài viết
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.
Ý 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.
Giải thuật
Bước 1: Chạy vòng lặp for (i = 0; i < n-1; i++) để di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp.
Bước 2: Chạy vòng lặp for (j = i+1; j < n; j++) để tìm số nhỏ nhất a[min] trong dãy số chưa sắp xếp.
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.
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:
- Chứng chỉ tin học IC3 là gì? Trường nào chấp nhận và sử dụng
- Google Scholar là gì? Các tính năng nổi bật của Google Scholar
- Cách trích dẫn tài liệu tham khảo đúng chuẩn trong luận văn tốt nghiệp
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!
