Thuật toán sắp xếp selection sort minh họa code sử dụng c++

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++.

Bài viết đầu tiên này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp selection sort. Nội dung bài viết bao gồm các phần sau:

  • Ý tưởng của thuật toán
  • Ví dụ minh họa
  • Minh họa thuật toán sử dụng ngôn ngữ C++
  • Đánh giá thuật toán

Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu

Ý tưởng của thuật toán selection sort

Minh họa thuật toán selection sort
Minh họa thuật toán selection sort

Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán sẽ chia mảng làm 2 mảng con

  1. Một mảng con đã được sắp xếp
  2. Một mảng con chưa được sắp xếp

Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.

Ví dụ minh họa

Minh họa thuật toán sử dụng ngôn ngữ C++

Kết quả chạy kiểm tra

Đánh giá thuật toán selection sort

Độ  phức tạp thuật toán

  • Trường hợp tốt: O(n^2)
  • Trung bình: O(n^2)
  • Trường hợp xấu: O(n^2)

Không gian bộ nhớ sử dụng: O(1)

Nếu thấy bài viết hay và bổ ích, hay like và follow fanpage Học lập trình cùng Nguyễn Văn Hiếu để nhận thông báo về những bài viết mới nhất nhé.

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
unless Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
unless
Guest
unless

mình nghĩ cái selectionsorf cái swap nên bỏ ngoài vòng for j