efficient_quick_sort.py

"""
ПРИНЦИП РАБОТЫ
    Как и в случае обычной быстрой сортировки, которая использует дополнительную память,
    необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив.
    Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем — большие опорного.

    Затем сортировка вызывается рекурсивно для двух полученных частей.
    Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память.

    Теперь разберёмся, как реализовать этот шаг in-place.
    Пусть мы как-то выбрали опорный элемент (рандомно!). Заведём два указателя left и right,
    которые изначально будут указывать на левый и правый концы отрезка соответственно.
    Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного.
    Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный.
    В итоге окажется, что левее от left все элементы точно принадлежат первой группе, а правее от right — второй.
    Элементы, на которых стоят указатели, нарушают порядок.
    Поменяем их местами и продвинем указатели на следующие элементы.
    Будем повторять это действие до тех пор, пока left и right не столкнутся.

ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
    Быстрая сортировка – разделяет коллекцию на две (примерно) равные части,
    принимая псевдослучайный элемент и используя его в качестве опоры (как бы центра деления).
    Элементы, меньшие, чем опора, перемещаются влево от опоры,
    а элементы, размер которых больше, чем опора, справа от него.
    Этот процесс повторяется для коллекции слева от опоры, а также для массива элементов справа от опоры,
    пока весь массив не будет отсортирован.

    Когда мы описываем элементы как «больше» или «меньше», чем другой элемент —
    это не обязательно означает большие или меньшие целые числа,
    мы можем отсортировать по любому выбранному нами свойству.

    Книга - Грокаем Алгоритмы А. Бхаргава.
    Статья - https://gb.ru/posts/python_sort.

ВРЕМЕННАЯ СЛОЖНОСТЬ
    Поскольку все операции разделения, проделываемые на одной глубине рекурсии,
    обрабатывают разные части исходного массива, размер которого постоянен,
    суммарно на каждом уровне рекурсии потребуется также O(n) операций, где n - количество элементов в массиве.
    Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии.
    Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
    В худшем случае размер стека описывается как O(n) - один из подмассивов всегда пуст на каждом уровне рекурсии,
    в лучшем случае он составит O(log n) - в качестве опорного элемента выбирается средний элемент.

    Лучший случай - О(n) * O(log n) = О(n * log n)
    Среднее - О(n * log n)
    Худший случай - О(n) * O(n) = О(n^2)

    Вики - https://ru.wikipedia.org/wiki/Быстрая_сортировка.

ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
    Требует лишь O(1) дополнительной памяти для своей работы.

"""
import random
from dataclasses import dataclass


@dataclass(frozen=True)
class User:
    __slots__ = ['username', 'solved', 'errors']
    username: str
    solved: int
    errors: int

#   Такой компаратор лучше сделать на основе сравнения ключа
#   В качестве ключа может использоваться кортеж
# 
#   def key(self):
#       return (-self.solved, self.errors, self.username)
#     
#   def __gt__(self, other):
#       return self.key() > other.key()

    def __gt__(self, other):
        if self.solved == other.solved:
            return self.username > other.username if self.errors == other.errors else self.errors > other.errors
        return self.solved < other.solved

    def __lt__(self, other):
        return other > self

    def __str__(self):
        return self.username


def quicksort(arr, low, high):
    if low >= high:
        return -1

    left, right = low, high
    pivot = arr[random.randint(low, high)]

    while left <= right:
        while arr[left] < pivot:
            left += 1
        while arr[right] > pivot:
            right -= 1
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1

    quicksort(arr, low=low, high=right)
    quicksort(arr, low=left, high=high)


n = int(input())
users = []

for _ in range(n):
    username, solved, errors = input().split()
    users.append(User(username, int(solved), int(errors)))

quicksort(users, low=0, high=n-1)

for person in users:
    print(person)