selection-sort-la-gi-thuat-toan-sap-xep-chon-selection-sort-trong-c-c

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é

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
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
Ý 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 < 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
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.
Input và Output
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!

Trả lời

Email của bạn sẽ không được hiển thị công khai.