-
Notifications
You must be signed in to change notification settings - Fork 0
/
efficient_quick_sort.py
99 lines (80 loc) · 2.68 KB
/
efficient_quick_sort.py
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# 68547597
def partition(persons: list, left: int, right: int) -> int:
"""Partition."""
pivot = persons[left]
i = left + 1
j = right - 1
while True:
if i <= j and persons[j] > pivot:
j -= 1
elif i <= j and persons[i] < pivot:
i += 1
elif (persons[j] > pivot) or (persons[i] < pivot):
continue
if i <= j:
persons[i], persons[j] = persons[j], persons[i]
else:
persons[left], persons[j] = persons[j], persons[left]
return j
def quick_sort(persons: list, left: int, right: int) -> None:
"""Quick sort."""
if (right - left) > 1:
p = partition(persons, left, right)
quick_sort(persons, left, p)
quick_sort(persons, p + 1, right)
def transformation(persons: list) -> list:
"""Transformation."""
persons[1] = -int(persons[1])
persons[2] = int(persons[2])
return [persons[1], persons[2], persons[0]]
if __name__ == '__main__':
number = int(input())
persons = [transformation(input().split()) for _ in range(number)]
left = 0
quick_sort(persons, left, len(persons))
print(*(list(zip(*persons))[2]), sep="\n")
# from dataclasses import dataclass
#
#
# @dataclass
# class Person():
# __slots__ = ('name', 'tasks_solved', 'fine')
# name: str
# tasks_solved: int
# fine: int
# def __post_init__(self):
# self.tasks_solved = -int(self.tasks_solved)
# def __lt__(self, other) -> bool:
# return ((self.tasks_solved, self.fine, self.name) <
# (other.tasks_solved, other.fine, other.name))
# def __repr__(self) -> str:
# return self.name
# def partition(persons: list, left: int, right: int) -> int:
# """Partition."""
# pivot = persons[left]
# i = left + 1
# j = right - 1
# while True:
# if i <= j and persons[j] > pivot:
# j -= 1
# elif i <= j and persons[i] < pivot:
# i += 1
# elif (persons[j] > pivot) or (persons[i] < pivot):
# continue
# if i <= j:
# persons[i], persons[j] = persons[j], persons[i]
# else:
# persons[left], persons[j] = persons[j], persons[left]
# return j
# def quick_sort(persons: list, left: int, right: int) -> None:
# """Quick sort."""
# if (right - left) > 1:
# p = partition(persons, left, right)
# quick_sort(persons, left, p)
# quick_sort(persons, p + 1, right)
# if __name__ == '__main__':
# number = int(input())
# persons = [Person(*input().split()) for _ in range(number)]
# left = 0
# quick_sort(persons, left, len(persons))
# print(*persons, sep="\n")