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

@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)

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@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 Супер-модератор 38169 / 21104 / 4307 Регистрация: 12.02.2012 Сообщений: 34,693 Записей в блоге: 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

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

Решение