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]
1
2
3

• 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]
1
2
3

• 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]
1
2
3

• Test case 4: Danh sách rỗng

arr = []
print(selection_sort(arr))
# Kết quả: []
1
2
3

• Test case 5: Danh sách chỉ có một phần tử

arr = [42]
print(selection_sort(arr))
# Kết quả: [42]
1
2
3

• 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]
1
2
3

• 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
1
2
3
4

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
1
2
3
4
5
6
7
8
9
10
11
12

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.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung 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). dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

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ÌNH LUẬ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.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK