Sắp xếp chọn – Minh họa trong Python và Scratch

Sắp xếp chọn – Minh họa trong Python và Scratch

Mình họa Sắp xếp chọn qua ví dụ cụ thể

Chúng ta sử dụng danh sách [4, 6, 3, 7, 14, 9] và áp dụng thuật toán sắp xếp chọn. Quá trình diễn ra như sau:

• Bước 1: Tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp, ở đây là 3. Hoán đổi 3 với phần tử đầu tiên của đoạn chưa được sắp xếp.
  • Danh sách sau bước này: [3, 6, 4, 7, 14, 9]
• Bước 2: Tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp từ vị trí thứ hai trở đi, ở đây là 4. Hoán đổi 4 với phần tử thứ hai của đoạn chưa được sắp xếp.
  • Danh sách sau bước này: [3, 4, 6, 7, 14, 9]
• Bước 3: Tiếp tục quá trình tương tự cho các phần tử còn lại. Tìm phần tử nhỏ nhất và hoán đổi vị trí nó với phần tử đầu đoạn chưa được sắp xếp.
  • Danh sách sau mỗi bước: [3, 4, 6, 7, 9, 14]
• Khi không còn đoạn chưa được sắp xếp nào, quá trình sắp xếp chọn kết thúc và kết quả là danh sách đã được sắp xếp: [3, 4, 6, 7, 9, 14] .

Triển khai thuật toán sắp xếp chọn (Selection Sort) bằng Python:

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # Tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp
        min_idx = i
        for j in range(i + 1, n):
            if arr[j]  < arr[min_idx] 



:
                min_idx = j
        
        # Hoán đổi phần tử nhỏ nhất với phần tử đầu đoạn chưa được sắp xếp
        arr[i] , arr[min_idx]  = arr[min_idx] , arr[i] 





    
    return arr

# Ví dụ sử dụng
arr = [4, 6, 3, 7, 14, 9] 


sorted_arr = selection_sort(arr)
print("Danh sách đã sắp xếp:", sorted_arr)

Kết quả: Danhsách đã sắpxếp: [3, 4, 6, 7, 9, 14]

Dưới đây là phân tích chi tiết về các câu lệnh trong thuật toán sắp xếp chọn (Selection Sort) ở trên:

1. Định nghĩa hàm selection_sort và truyền danh sách cần sắp xếp (arr) vào hàm.
2. Gán biến n bằng độ dài của danh sách (len(arr)). Biến n đại diện cho số lượng phần tử trong danh sách.
3. Bắt đầu vòng lặp for i in range(n) để duyệt qua từng vị trí trong danh sách.
4. Trong vòng lặp ngoài, khởi tạo biến min_idx và gán giá trị i cho nó. Biến min_idx sẽ lưu chỉ số của phần tử nhỏ nhất trong đoạn chưa được sắp xếp.
5. Bắt đầu vòng lặp for j in range(i + 1, n) để duyệt qua từng phần tử trong đoạn chưa được sắp xếp, bắt đầu từ phần tử tiếp theo sau phần tử hiện tại.
6. Trong vòng lặp này, ta kiểm tra nếu phần tử tại arr[j] nhỏ hơn phần tử nhỏ nhất hiện tại (arr[min_idx] ), thì ta gán giá trị j cho min_idx. Điều này sẽ cập nhật chỉ số của phần tử nhỏ nhất trong đoạn chưa được sắp xếp.
7. Sau khi vòng lặp for j kết thúc, ta đã tìm được chỉ số min_idx của phần tử nhỏ nhất trong đoạn chưa được sắp xếp.
8. Tiếp theo, ta hoán đổi vị trí của phần tử nhỏ nhất (arr[min_idx] ) với phần tử đầu đoạn chưa được sắp xếp (arr[i] ). Ta sử dụng cú pháp hoán đổi giá trị trong Python bằng cách sử dụng gán đồng thời (arr[i] , arr[min_idx] = arr[min_idx] , arr[i] ).
9. Quá trình hoán đổi này đảm bảo rằng phần tử nhỏ nhất sẽ được đưa vào đúng vị trí đầu của đoạn chưa được sắp xếp.
10. Tiếp tục vòng lặp for i cho đến khi duyệt qua tất cả các phần tử trong danh sách.
11. Khi vòng lặp for i kết thúc, danh sách đã được sắp xếp và ta trả về danh sách đã sắp xếp (arr).
12. Kết thúc định nghĩa hàm selection_sort.
13. Tạo một danh sách (arr) và gán giá trị vào danh sách. Trong ví dụ này, danh sách được gán giá trị là [4, 6, 3, 7, 14, 9] .
14. Gọi hàm selection_sort(arr) để sắp xếp danh sách.
15. In danh sách đã sắp xếp ra màn hình.

Sắp xếp chọn (Selection Sort) minh họa bằng Scratch