Selection Sort Visualization

🐢 🐇 Trung bình

Lượt chọn

Vị trí i

minIndex

Số lần swap

Đã sắp xếp

Chưa sắp xếp

Min hiện tại

Đang so sánh

Nhấn "Bắt đầu sắp xếp" để xem thuật toán hoạt động.

🎯 Kết luận

Selection Sort: chọn min mỗi lượt; số swap ít; vẫn O(n²).

🐍 Code Python

def selection_sort(arr):
    """
    Thuật toán Selection Sort (Sắp xếp chọn)
    
    Ý tưởng:
    - Chia mảng thành 2 phần: đã sắp xếp (bên trái) và chưa sắp xếp (bên phải)
    - Mỗi lượt: tìm phần tử nhỏ nhất trong phần chưa sắp xếp
    - Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của phần chưa sắp xếp
    - Mở rộng vùng đã sắp xếp sang phải 1 vị trí
    
    Độ phức tạp:
    - Thời gian: O(n²) - cả 3 trường h���p (tốt nhất, trung bình, xấu nhất)
    - Không gian: O(1) - sắp xếp tại chỗ (in-place)
    
    Ưu điểm:
    - Số lần hoán đổi ít nhất: O(n)
    - Phù hợp khi chi phí hoán đổi lớn (ví dụ: hoán đổi vật lý)
    - Đơn giản, dễ hiểu
    
    Nhược điểm:
    - Không hiệu quả với dữ liệu lớn
    - Không ổn định (có thể thay đổi thứ tự các phần tử bằng nhau)
    """
    n = len(arr)
    swap_count = 0  # Đếm số lần hoán đổi
    
    # Duyệt qua từng vị trí trong mảng (trừ vị trí cuối)
    for i in range(n - 1):
        # Giả sử phần tử ��ầu tiên của phần chưa sắp xếp là nhỏ nhất
        min_index = i
        
        # Tìm phần tử nhỏ nhất trong phần còn lại
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # Cập nhật vị trí phần tử nhỏ nhất
        
        # Nếu tìm thấy phần tử nhỏ hơn, hoán đổi
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            swap_count += 1
            print(f"Lượt {i+1}: Hoán đổi {arr[min_index]} ↔ {arr[i]}")
            print(f"Mảng hiện tại: {arr}")
    
    print(f"\nTổng số lần hoán đổi: {swap_count}")
    return arr


# Ví dụ sử dụng
if __name__ == "__main__":
    # Mảng cần sắp xếp
    arr = [64, 25, 12, 22, 11, 90, 34, 50]
    
    print("Mảng ban đầu:", arr)
    print("\n--- Bắt đầu sắp xếp ---\n")
    
    result = selection_sort(arr.copy())
    
    print("\n--- Kết quả ---")
    print("Mảng đã sắp xếp:", result)
    
    # So sánh với các thuật toán khác
    print("\n📊 So sánh Selection Sort với các thuật toán khác:")
    print("┌─────────────────┬──────────────┬───────────────┬──────────────┐")
    print("│ Thuật toán      │ Thời gian TB │ Số lần swap   │ Ổn định      ��")
    print("├─────────────────┼──────────────┼───────────────┼──────────────┤")
    print("│ Selection Sort  │ O(n²)        │ O(n) - ÍT     │ Không        │")
    print("│ Bubble Sort     │ O(n²)        │ O(n²) - NHIỀU │ Có           │")
    print("│ Insertion Sort  │ O(n²)        │ O(n²)         │ Có           │")
    print("│ Quick Sort      │ O(n log n)   │ O(n log n)    │ Không        │")
    print("│ Merge Sort      │ O(n log n)   │ 0 (dùng copy) │ Có           │")
    print("└─────────────────┴──────────────┴───────────────┴──────────────┘")