# Principled Programming / Tim Teitelbaum / Chapter 11.

# QuickSort.
def quick_sort_aux(A: list[int], L: int, R: int)-> None:
    """Given A[L..R-1], quick_sort_aux(A,L,R) rearranges A[L..R-1] into <p, ==p, and >p regions."""
    if R > L:

        # Compute the pivot p.
            p: int = (A[L] + A[R-1]) // 2

        # ⟨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⟩

        # Partitioning both halves recursively.
            quick_sort_aux(A, L, w)
            quick_sort_aux(A, b, R)

def quick_sort(A:list[int], n:int) -> None:
    """Rearrange values of A[0..n-1] into non-decreasing order."""
    quick_sort_aux(A, 0, n)

def e11_1_1() -> None:
    A: list[int] = fresh()

    print("QuickSort has sorted", A, end='')
    quick_sort(A, len(A))
    if is_sort_correct(A): print(" correctly.")
    else: print(" incorrectly.")

# MergeSort.
def merge_sort_aux(A: list[int], L: int, R: int) -> None:
    """Rearrange values of A[L..R] into non-decreasing order."""
    if R > L:
        m: int = (L + R) // 2
        merge_sort_aux(A, L, m)     # Sort left half.
        merge_sort_aux(A, m + 1, R) # Sort right half.

        # Given A[L..m] and A[m+1..R], both already in non-decreasing order,
        # collate them so A[L..R] is in non-decreasing order.

        # This is the subject of Exercises 66 and 67 in the book, and is
        # therefore left  unfinished here. The difficult part is minimizing
        # copying since collation in situ is not possible.

def merge_sort(A: list[int], n: int):
    """Rearrange values of A[0..n-1] into non-decreasing order."""
    merge_sort_aux(A, n, len(A)-1)

def e11_2_1() -> None:
    print("Implementation of MergeSort is incomplete.")

# Selection Sort.
def selection_sort(A: list[int], n: int):
    """Rearrange values of A[0..n-1] into non-decreasing order. """
    for j in range(0, n - 1):
        # Let k be s.t. A[k] is a minimal value in A[j..n-1].
            k = j
            for i in range(j + 1, n):
                if A[i] < A[k]: k = j
        # Swap A[j] and A[k]. */
            temp = A[j]
            A[j] = A[k]
            A[k] = temp

def e11_3_1() -> None:
    A: list[int] = fresh()

    print("SelectionSort has sorted", A, end='')
    quick_sort(A, len(A))
    if is_sort_correct(A):
        print(" correctly.")
    else:
        print(" incorrectly.")

# Insertion Sort.
def insertion_sort(A: list[int], n: int):
    """Rearrange values of A[0..n-1] into non-decreasing order."""
    for j in range(1, n):
        # Given A[0..j-1] ordered in non-decreasing order, rearrange
        #   values of A[0..j] so it is ordered.

        # Save A[j]
            temp = A[j]
        # Shift A[k..j-1] right one place, where k is the largest
        #   integer s.t. A[k-1]≤temp, or 0 if temp is smallest.
            k = j
            while (k > 0) and (A[k - 1] > temp):
                A[k] = A[k - 1]
                k -= 1
        # Put temp back where it belongs.
            A[k] = temp

def e11_4_1() -> None:
    """Test Insertion Sort. """
    A: list[int] = fresh()

    print("InsertionSort has sorted", A, end='')
    insertion_sort(A, len(A))
    if is_sort_correct(A):
        print(" correctly.")
    else:
        print(" incorrectly.")

# Utility.
def fresh() -> list[int]:
    """Provide a fresh copy of the test array sample."""
    sample: list[int] = [80, 60, 40, 20, 70, 50, 30, 10]
    return sample.copy()

def is_sort_correct(A: list[int]) -> bool:
    answer: list[int] = [10, 20, 30, 40, 50, 60, 70, 80]
    return A == answer

# Uncomment out to run.
e11_1_1()
#e11_2_1()
#e11_3_1()
#e11_4_1()