effective quick sort

package sprint3.xb

import java.io.BufferedWriter

/**
 * ПРИНЦИП РАБОТЫ
 * Алгоритм осуществляет быструю сортировку в соответствии с компаратором, переданным в [less]. Для того чтобы избежать
 * использования дополнительной памяти, используется подход in-place sort. На каждом этапе случайным образом выбирается
 * опорный элемент, и, после перестановок, слева от опорного элемента оказываются значения меньшие его, а справа -
 * значения большие. Далее сортировка осуществляется рекурсивно для обеих частей до тех пор, пока не будет достигнут
 * базовый случай.
 *
 * ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
 *
 *
 * ВРЕМЕННАЯ СЛОЖНОСТЬ
 * В среднем поиск выполняется со сложностью быстрой сортировки - O(n log n)
 *
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
 * Пространственная сложность O(n), т.к. для поиска используется исходный массив, дополнительная память не требуется.
 *
 * @param subArrayStart индекс начала сортируемой части массива (включительно)
 * @param subArrayEnd индекс конца сортируемой части массива (включительно)
 * @param less компаратор, возвращающий true, если первый аргумент меньше второго аргумента
 */
fun <T : Any> inPlaceQuickSort(array: Array<T>, subArrayStart: Int, subArrayEnd: Int, less: (T, T) -> Boolean) {
    // в ином случае размер сортируемой части подмассива меньше 1, а значит сортировать нечего (базовый случай)
    if (subArrayStart < subArrayEnd) {
        val pivot = array[(subArrayStart..subArrayEnd).random()] // значение опорного элемента
        var left = subArrayStart
        var right = subArrayEnd
        while (left <= right) {
            while (less(array[left], pivot)) {
                left++
            }
            // в этом месте все элементы list от 0 до left (не включительно) меньше опорного элемента
            while (less(pivot, array[right])) {
                right--
            }
            // в этом месте все элементы list от right (не включительно) до sublistEnd больше опорного элемента
            if (left <= right) {
                array[left] = array[right].also { array[right] = array[left] }
                left++
                right--
            }
        }
        inPlaceQuickSort(array, subArrayStart, right, less)
        inPlaceQuickSort(array, left, subArrayEnd, less)
    }
}

/**
 * Сравнение представлений стажёров.
 *
 * @return true, если [intern1] выше по рейтингу (имеет меньшее - less - значение рейтинга), чем [intern2]
 */
fun less(intern1: Intern, intern2: Intern): Boolean {
    return if (intern1.taskCount != intern2.taskCount) {
        intern1.taskCount > intern2.taskCount
    } else if (intern1.penalty != intern2.penalty) {
        intern1.penalty < intern2.penalty
    } else {
        intern1.name < intern2.name
    }
}

/**
 * Представление стажёра.
 */
data class Intern (
    val name: String,
    val taskCount: Int,
    val penalty: Int
)

fun main() {
    val reader = System.`in`.bufferedReader()
    val writer = System.out.bufferedWriter()
    val count = reader.readLine().toInt()
    val inputStrings = Array<String>(count) {
        reader.readLine()
    }
    val interns = inputStrings.map { it.split(" ") }
        .map { Intern(name = it[0], taskCount = it[1].toInt(), penalty = it[2].toInt()) }
        .toTypedArray()
    inPlaceQuickSort(interns, 0, interns.lastIndex) {
        intern1, intern2 -> less(intern1, intern2)
    }
    with(writer) {
        interns.forEach {
            handleResult(it.name)
        }
        flush()
    }
}

private fun BufferedWriter.handleResult(result: String) {
    write(result)
    newLine()
}