Эффективная быстрая сортировка

@thegho · Регистрация: 22.08.2021

Студворк — интернет-сервис помощи студентам

Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.

Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач Pi и размер штрафа Fi. Штраф начисляется за неудачные попытки и время, затраченное на задачу.

Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.

Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").

Как работает in-place quick sort
Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.

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

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

Формат ввода

В первой строке задано число участников n, 1 ≤ n ≤ 100 000. В каждой из следующих n строк задана информация про одного из участников. i-й участник описывается тремя параметрами: уникальным логином (строкой из маленьких латинских букв длиной не более 20) числом решённых задач Pi штрафом Fi Fi и Pi — целые числа, лежащие в диапазоне от 0 до 109.

Формат вывода
Для отсортированного списка участников выведите по порядку их логины по одному в строке.

Пример 1:

Ввод

Code
1
2
3
4
5
6
5
alla 4 100
gena 6 1000
gosha 2 90
rita 2 90
timofey 4 80

Вывод:

Code
1
2
3
4
5
gena
timofey
alla
gosha
rita

Пример 2:

Code
1
2
3
4
5
6
5
alla 0 0
gena 0 0
gosha 0 0
rita 0 0
timofey 0 0

Вывод

Code
1
2
3
4
5
alla
gena
gosha
rita
timofey

@eaa · 05.09.2021, 20:23

И? что не получается конкретно?

@Catstail · 06.09.2021, 09:13

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def quick_sort(arr,left,right):
    if left>=right:
        return
    mid=(left+right)//2
    sep=arr[mid]
    i=left
    j=right
    while True:
        while arr[i]<sep:
            i+=1
        while arr[j]>sep:
            j-=1
        if (i<=j):
            arr[i],arr[j]=arr[j],arr[i]
            i+=1
            j-=1
        if (i>j):
            break
    quick_sort(arr,left,j)
    quick_sort(arr,i,right)
 
x=[1,2,3,1,2,3,1,2,3,22,-5,12,0]
 
quick_sort(x,0,len(x)-1)
 
print(x)

Это классическая реализация quick sort. Но она тоже расходует оперативную память (рекурсия ведь чего-то стоит)...

@thegho · 06.09.2021, 13:23 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Studunit:
    def __init__(self, name, tasks_solved, penalty):
        self.name = name
        self.tasks_solved = tasks_solved
        self.penalty = penalty
 
    def __str__(self):
        return self.name
 
 
def main() -> None:
    length = int(input())
    participants = []
    for i in range(length):
        name, tasks, penalty = input().split()
        participants.append(Studunit(name, int(tasks), int(penalty)))
 
    print(*participants, sep='\n')
 
 
if __name__ == '__main__':
    main()

пытаюсь сделать сортировки

@Arsegg · 06.09.2021, 14:09

Catstail, Iterative Quick Sort.

@Catstail · 06.09.2021, 14:38

Arsegg, от рекурсии, полагаю, можно отказаться, если использовать стек. Но память все равно будет нужна.

@dnscheb · 06.09.2021, 21:45

Python
1
2
3
4
5
6
7
8
def quicksort(data):
    if data < 2:
        return data
    else:
        pivot = data[0]
        less = [i for i in data[1:] if i <= pivot]
        greater = [j for j in data[1:] if j > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

@Garry Galler · 07.09.2021, 01:04

dnscheb это неэффективный рекурсивный школьный вариант.
Вот так как раз делать не надо.

@Arsegg · 07.09.2021, 02:04

Хоть и не quick sort, но не составит никакого труда его реализовать самостоятельно:

Python
1
2
3
4
5
6
7
def toParticipant(login, p, f):
    return (-int(p), int(f), login)
    
n = int(input())
participants = sorted(toParticipant(*input().split()) for _ in range(n))
result = (login for _, _, login in participants)
print(*result, sep="\n")

@dnscheb · 07.09.2021, 10:50

Сообщение от Garry Galler

dnscheb это неэффективный рекурсивный школьный вариант.
Вот так как раз делать не надо.

этот вариант плох из за ограничения стека вызовов?

@Arsegg · 07.09.2021, 11:36

dnscheb, не только: мало того, что данное решение требует O(N) памяти в рамках одного вызова функции, так еще, потенциально, может O(N * log(N)) в итоге из-за рекурсии.

@Catstail · 08.09.2021, 18:48

Вот честное решение - быстрая сортировка без рекурсии (со стеком):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def quick_sort_rec(arr):
    stack=[]
    def part_sort(left,right):
        print(left,right)
        if right-left<=1:
            return
        mid=(left+right)//2
        sep=arr[mid]
        i=left
        j=right
        while True:
            while arr[i]<sep:
                i+=1
            while arr[j]>sep:
                j-=1
            if (i<=j):
                arr[i],arr[j]=arr[j],arr[i]
                i+=1
                j-=1
            if (i>j):
                stack.append((left,j))
                stack.append((i,right))
                return
    stack.append((0,len(arr)-1))
    while True:
        if len(stack)==0:
            return
        (l,r)=stack.pop()
        part_sort(l,r)
        
x=[1,2,3,1,2,3,1,2,3,22,-5,12,0]
 
quick_sort_rec(x)
 
print(x)

Новые блоги и статьи Все статьи Все блоги /
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .
1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	05.09.2021, 20:23
	И? что не получается конкретно? 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	06.09.2021, 14:09
	Catstail, Iterative Quick Sort. 1

@Catstail Супер-модератор 38193 / 21126 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	06.09.2021, 14:38
	Arsegg, от рекурсии, полагаю, можно отказаться, если использовать стек. Но память все равно будет нужна. 0

@Garry Galler 5438 / 3859 / 1215 Регистрация: 28.10.2013 Сообщений: 9,552 Записей в блоге: 1
	07.09.2021, 01:04
	dnscheb это неэффективный рекурсивный школьный вариант. Вот так как раз делать не надо. 1

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	07.09.2021, 11:36
	dnscheb, не только: мало того, что данное решение требует `O(N)` памяти в рамках одного вызова функции, так еще, потенциально, может `O(N * log(N))` в итоге из-за рекурсии. 0

Эффективная быстрая сортировка

Решение