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

6
14694
Thuât toán 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

Nội dung bài viết

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

6 BÌNH LUẬN

  1. có chỗ em thắc mắc như em thêm dòng code
    cout << "min =" << min<< " j="<< j <<" "<<" i="<< i<< endl;
    cout<< "a[min]="<<a[min]<<" a[j]="<<a[j]<<endl;
    trước if (arr[j] < arr[min_idx])
    min_idx = j;
    sao lại mất mất dòng min =0; i=0; j=1; chỉ hiển thị các dòng sau đó từ min =1; j=2;i=0;
    em viết cout << "min =" << min<< endl;
    cout << " j="<< j <<" "<<" i="<< i<< endl;
    thì lại hiển thị đầy đủ

    • Sao em thử với dãy 6,4,3,9 nó lại cho kết quả sai nhỉ, thử với dãy số cuối nhỏ hơn số đầu như 6,4,3,2 lại đúng nhưng 6,4,3,8 lại sai

ĐỂ LẠI BÌNH LUẬN

Vui lòng nhập nội dung bình luận
Vui lòng nhập tên

Website này sử dụng Akismet để hạn chế spam. Tìm hiểu bình luận của bạn được duyệt như thế nào.