# Principled Programming / Tim Teitelbaum / Chapter 10.

def quick_select(A: list[int], n: int, j: int) -> int:
    """Given A[0..n-1], and int 0≤j<n, quick_select(A,n,j) returns the j-th
    smallest value in A[0..n-1].
    """
    L = 0;  R = n
    while (R - L) > 1:
        # Compute pivot p, and partition relative to p.
            p = (A[L] + A[R - 1]) // 2     # value of pivot

        # ⟨BEGIN body of partition⟩
        # A[L..w-1]<p, A[w..k-1]==p, A[b..R-1]>p, for L≤w≤k≤b≤R.
            w: int = L;   k: int = L;  b: int = R
            temp: int
            while k != b:
                if A[k] > p:
                    # Swap A[b-1] and A[k].
                        temp = A[b - 1];  A[b - 1] = A[k];  A[k] = temp
                    #
                        b -= 1
                elif A[k] < p:
                    # Swap A[w] and A[k]. */
                        temp = A[k];  A[k] = A[w];   A[w] = temp
                    #
                        k += 1;  w += 1
                else:  # A[k]==p
                        k += 1
        # ⟨END body of partition⟩

        # Go on to “<p” or “>p” region if j-th smallest there; else return p.
            if j < w: R = w
            elif j < b: return p
            else: L = b
    return A[j]

def e10_1_1():
    """Test quick select."""
    for j in range(8):
        A: list[int] = [10, 20, 15, 25, 5, 3, 22, 1]
        n: int = len(A)

        print("The", j, "-th smallest value in", A, "is ", end='')
        print(quick_select(A, n, j))

# Uncomment out to run.
#e10_1_1()