Sắp xếp một danh sách các số nguyên bằng thuật toán sắp xếp chọn(Selection sort).

Bài tập giải thuật với Python

0.0 (0 đánh giá)
Tạo bởi Kteam Cập nhật lần cuối 00:17 05-05-2023 737 lượt xem 0 bình luận
Tác giả/Dịch giả: K9
Học nhanh

Danh sách bài học

Sắp xếp một danh sách các số nguyên bằng thuật toán sắp xếp chọn(Selection sort).

Yêu cầu bài toán

Viết một chương trình Python để sắp xếp một danh sách các số nguyên bằng thuật toán sắp xếp chọn(selection sort).


Thuật toán sắp xếp chọn - Selection Sort

Thuật toán sắp xếp chọn (Selection Sort) là một trong những thuật toán sắp xếp cơ bản, dùng để sắp xếp một danh sách theo thứ tự tăng dần hoặc giảm dần.

Ý tưởng của thuật toán là duyệt qua từng phần tử trong danh sách và tìm phần tử nhỏ nhất (đối với sắp xếp tăng dần) hoặc lớn nhất (đối với sắp xếp giảm dần) trong các phần tử còn lại. Sau đó, đổi chỗ phần tử nhỏ nhất/lớn nhất với phần tử đang xét. Thuật toán tiếp tục thực hiện việc này cho đến khi danh sách được sắp xếp hoàn toàn.

Các bước thực hiện thuật toán sắp xếp chọn như sau:

  1. Bắt đầu từ vị trí đầu tiên trong danh sách, tìm phần tử nhỏ nhất/lớn nhất trong danh sách còn lại.

  2. Sau khi tìm được phần tử nhỏ nhất/lớn nhất, đổi chỗ phần tử đó với phần tử ở vị trí đầu tiên.

  3. Tiếp tục tìm phần tử nhỏ nhất/lớn nhất trong danh sách còn lại bắt đầu từ vị trí thứ hai, đổi chỗ phần tử đó với phần tử ở vị trí thứ hai.

  4. Lặp lại quá trình trên cho đến khi danh sách được sắp xếp hoàn toàn.

Lưu ý: Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), nghĩa là độ phức tạp của thuật toán tăng theo bình phương số lượng phần tử trong mảng. Vì vậy, thuật toán này không phù hợp với việc sắp xếp các mảng lớn.

Giải thích qua ví dụ

Xét qua mảng sau arr[] = {64, 25, 12, 22, 11}

Duyệt lần 1:  Toàn bộ mảng được duyệt tuần tự từ vị trí 0 đến 4. Bắt đầu với giá trị 64 ở vị trí 0, sau khi duyệt qua toàn bộ mảng, có thể thấy 11 là giá trị thấp nhất.

arr[ ] 64 25 12 22 11
index 0 1 2 3 4
  • Do đó, thay thế giá trị 11 vào vị trí 0 (vị trí đầu tiên) và giá trị 64 vào vị trí 4.

Duyệt lần 2: Duyệt tuần tự từ vị trí 1 đến 4. Bắt đầu với giá trị 25 ở vị trí 1. Sau khi duyệt qua, ta thấy giá trị 12 ở vị trí 2 nhỏ nhất trong mảng.

arr[ ] 11 25 12 22 64
index 0 1 2 3 4
  • Do đó, thay thế giá trị 12 vào vị trí 1(vị trí thứ hai) và giá trị 25 vào vị trí 2. 

Duyệt lần 3: Duyệt tuần tự từ vị trí 2 đến 4. Bắt đầu với giá trị 25 ở vị trí 2. Sau khi duyệt qua, ta thấy giá trị 22 ở vị trí 3 nhỏ nhất trong mảng.

arr[ ] 11 12 25 22 64
index 0 1 2 3 4
  • Do đó, thay thế giá trị 22 vào vị trí 2 (vị trí thứ ba) và giá trị 25 vào vị trí 3. 

Duyệt lần 4: Duyệt tương tự. Bắt đầu với giá trị 25 ở vị trí 3. Sau khi duyệt qua, ta thấy giá trị 25 ở vị trí 3 nhỏ nhất trong mảng.

arr[ ] 11 12 22 25 64
index 0 1 2 3 4
  • Do đó, giữ nguyên vì giá trị 25 đang ở vị trí 3 (vị trí thứ tư)

Duyệt lần 5: Cuối cùng, giá trị lớn nhất có mặt trong mảng sẽ tự động đặt ở vị trí cuối cùng trong mảng, giá trị 64 ở vị trí 4

Ta có được mảng đã sắp xếp là

arr[ ] 11 12 22 25 64
index 0 1 2 3 4

Để bạn có thể hiểu rõ hơn, Kteam sẽ cho một ví dụ khác. Bạn hãy thử tự giải thích tuần tự cách sắp xếp chọn của ví dụ sau và trả lời đáp án vào bên dưới bình luận 

Ví dụ: Giải thích cách sắp xếp mảng arr = [29, 10, 14, 37, 14] với thuật toán sắp xếp chọn.


Định hướng cách làm

Để giải quyết bài toán sắp xếp một danh sách số nguyên bằng thuật toán sắp xếp chọn, bạn có thể định hướng như sau:

  1. Tạo hàm selection_sort với tham số đầu vào là một danh sách arr.
  2. Lấy chiều dài của danh sách bằng hàm len() và lưu vào biến n.
  3. Bắt đầu vòng lặp ngoài cùng, duyệt qua danh sách từ đầu đến cuối.
  4. Tại mỗi vòng lặp, tìm phần tử nhỏ nhất trong danh sách còn lại bắt đầu từ vị trí hiện tại bằng cách duyệt qua danh sách từ vị trí i+1 đến cuối danh sách. Lưu vị trí của phần tử nhỏ nhất vào biến min_idx.
  5. Đổi chỗ phần tử ở vị trí i với phần tử nhỏ nhất tìm được ở bước trên.
  6. Lặp lại các bước 4-5 cho đến khi danh sách được sắp xếp hoàn toàn.
  7. Trả về danh sách đã được sắp xếp.

Kết quả đầu ra sẽ là danh sách đã được sắp xếp theo thứ tự tăng dần.


Testcase

Bạn có thể sử dụng một số bộ test để kiểm tra tính đúng đắn của chương trình:

  • Test case 1: Danh sách đã sắp xếp
arr = [1, 2, 3, 4, 5]
print(selection_sort(arr))
# Kết quả: [1, 2, 3, 4, 5]
  • Test case 2: Danh sách ngược thứ tự
arr = [5, 4, 3, 2, 1]
print(selection_sort(arr))
# Kết quả: [1, 2, 3, 4, 5]
  • Test case 3: Danh sách có phần tử trùng nhau
arr = [3, 2, 4, 3, 1]
print(selection_sort(arr))
# Kết quả: [1, 2, 3, 3, 4]
  • Test case 4: Danh sách rỗng
arr = []
print(selection_sort(arr))
# Kết quả: []
  • Test case 5: Danh sách chỉ có một phần tử
arr = [42]
print(selection_sort(arr))
# Kết quả: [42]
  • Test case 6: Danh sách chứa các số âm
arr = [-2, 5, 0, -9, 3]
print(selection_sort(arr))
# Kết quả: [-9, -2, 0, 3, 5]
  • Test case 7: Danh sách lớn
import random
arr = [random.randint(-1000, 1000) for _ in range(10000)]
print(selection_sort(arr))
# Kết quả: Danh sách đã được sắp xếp tăng dần

Source code tham khảo

def selection_sort(arr):
    """
    Sắp xếp một danh sách số nguyên bằng thuật toán sắp xếp chọn
    """
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Kết luận

Mặc dù bài giảng được hướng dẫn với ngôn ngữ python nhưng bạn hoàn toàn có thể diễn đạt bài toán này bằng các ngôn ngữ C++, C#, Java, ... một cách tương tự.

Nếu bạn có cách làm hiệu quả hơn / tối ưu hơn, hoặc cách diễn đạt dễ hiểu hơn hãy để lại source code hoặc hướng dẫn bên dưới bình luận để mọi người có thể tham khảo và học hỏi thêm.


Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Bài tập giải thuật với Python

Khoá học Bài tập giải thuật lập trình với Python  bao gồm 100 bài tập lập trình giải thuật từ cơ bản đến nâng cao, giúp bạn rèn luyện và nâng cao kỹ năng tư duy, tự giải quyết các vấn đề khi gặp một bài toán lập trình. 

Bạn hoàn toàn có thể tự mình giải quyết các bài toán hoặc tham khảo source code mẫu, debug, theo dõi hướng dẫn của Kteam để trau dồi kinh nghiệm xử lý của mình.

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.