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


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:
-
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.
-
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.
-
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.
-
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:
- Tạo hàm
selection_sort
với tham số đầu vào là một danh sácharr
. - Lấy chiều dài của danh sách bằng hàm
len()
và lưu vào biếnn
. - Bắt đầu vòng lặp ngoài cùng, duyệt qua danh sách từ đầu đến cuối.
- 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ếnmin_idx
. - Đổi chỗ phần tử ở vị trí
i
với phần tử nhỏ nhất tìm được ở bước trên. - 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.
- 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ả

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.