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

Thuật ngữSelection sort là gì? Thuật toán sắp xếp chọn Selection sort trong...

Ngày đăng:

0
(0)

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é

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

Xem thêm:

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!

Bạn thấy bài viết này hữu ích chứ?

Hãy chọn vào ngôi sao để đánh giá bài viết

Đánh giá trung bình 0 / 5. Lượt đánh giá 0

Hãy là người đầu tiên đánh giá bài viết

Hãy để lại bình luận

Xem nhiều

Bài tin liên quan

Trôn Việt Nam là gì? Vì sao hot rần rần trên TikTok, Facebook?

Những ngày gần đây, giới trẻ bỗng rần rần...

Status là gì? Cách đăng Status lên Facebook, Zalo nhanh, đơn giản nhất

Mạng xã hội dần trở nên phổ biến với...

Cách làm mứt dừa non thơm bùi, mềm dẻo với công thức chuẩn nhất đón Tết

Mứt dừa là loại mứt không thể thiếu trên...

Light novel là gì? Sự khác biệt giữa light novel và manga/anime

Light novel là một khái niệm quen thuộc với...