Chọn phần tử nhỏ thứ n từ List trong thời gian tuyến tính Python

Thuật toán Quickselect tìm phần tử nhỏ thứ i (i=1 là nhỏ nhất). Partition tương tự nhưng logic so sánh ngược.

Ví dụ

def select_smallest(arr, left, right, i):
    if right - left <= 1:
        return arr[left]
    pivot_idx = partition(arr, left, right)
    k = pivot_idx - left + 1  # số phần tử <= pivot
    if i < k:
        return select_smallest(arr, left, pivot_idx, i)
    elif i > k:
        return select_smallest(arr, pivot_idx + 1, right, i - k)
    return arr[pivot_idx]

def partition(arr, left, right):
    pivot = arr[left]
    i = left + 1
    j = right - 1
    while True:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            arr[left], arr[j] = arr[j], arr[left]
            return j

arr = list(map(int, input("Nhập dãy số: ").split()))
i = int(input("Nhập i (1 là nhỏ nhất): "))
print("Kết quả:", select_smallest(arr, 0, len(arr), i))

Kết quả

Nhập dãy số: 43 12 67 89 99 0
Nhập i (1 là nhỏ nhất): 3
Kết quả: 43

Giải thích

• Partition giống bài lớn thứ n, nhưng k = pivot_idx - left + 1 (số phần tử <= pivot).
• Nếu i < k: tìm bên trái pivot; i > k: tìm bên phải với i-k.
• Trung bình O(n).