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

Sắp xếp chọn là gì? Giới thiệu giải thuật Selection sort trong C/C++ giúp sắp xếp mảng theo thứ tự đơn giản, nhanh chóng. Xem thêm thuật toán Selection sort có code mẫu

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 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é

Selection sort

I. Sắp xếp chọn - Selection sort là gì?

1. 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

2. Ý tưởng

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

3. 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.

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

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

1. Code minh họa

2. 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.

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!

Trung tâm chuyên sửa chữa thay thế, bảo hành miễn phí, nhượng quyền thương hiệu trungtambaohanh.com + marketing.