/*
 * Quicksort.kt
 * 
 * This is Dave Musicant's Quicksort.kt from Fall 2024,
 * which was ported by Dave from the Quicksort code at
 * https://opendsa-server.cs.vt.edu/OpenDSA/Books/Everything/html/Quicksort.html
 * 
 * Modified lightly by Tanya Amert for Spring 2025.
 * 
 * Implements the Quicksort algorithm.
 */

// Swap the elements at two specified positions in a list.
fun <T> swap(list: MutableList<T>, i: Int, j: Int) {
    val temp = list[i]
    list[i] = list[j]
    list[j] = temp
}

// Perform quicksort on the sublist from indices i..j in the list A.
fun <T: Comparable<T>> quicksort(A: MutableList<T>, i: Int, j:Int) {
    // Pick a pivot
    val pivotindex = findpivot(i, j)

    // Swap the pivot to position j
    swap(A, pivotindex, j)

    // Partition the sublist in indices i..j-1 around the pivot;
    // the value k is the first position in the right subarray
    val k = partition(A, i, j-1, A[j])

    // Swap the pivot into its place between the two partitions
    swap(A, k, j)

    // Recursively call quicksort on the two partitions
    if ((k-i) > 1) { quicksort(A, i, k-1) }  // left partition
    if ((j-k) > 1) { quicksort(A, k+1, j) }  // right partition
}

// Find the pivot as the midpoint in i..j, rounded down.
fun findpivot(i: Int, j: Int): Int {
    return (i+j)/2
}

// Partition the sublist at positions leftStart..rightStart in A around the pivot.
fun <T: Comparable<T>> partition(A: MutableList<T>, leftStart: Int, rightStart: Int, pivot: T): Int {
    var left = leftStart
    var right = rightStart

    // Move the bounds inward until they meet (then it's partitioned)
    while (left <= right) {
        // Move from L->R until we hit something bigger than (or same as) the pivot
        while (A[left] < pivot) { left++ }

        // Move from R->L until we hit something smaller than the pivot, or they cross
        while ((right >= left) && (A[right] >= pivot)) { right-- }

        // Swap the two values that made us stop (on the L it was >=pivot, on the R
        // it was <pivot)
        if (right > left) { swap(A, left, right) }

        // If we haven't cross left and right indices, then we'll try again to keep partitioning
    }

    // We'll return the first position in the right partition, which is the
    // location where the pivot should be to be between partitions
    return left
}

// Test our quicksort code.
fun main() {
    var list = mutableListOf(10, 4, 2, 1, 20, 29, 3, 2, 6)
    quicksort(list, 0, list.count()-1)
    println(list)
}