py_scripts/fastSort.py at master · Burya94/py_scripts · GitHub

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
#!/usr/bin/python3

c = 0

def count_c(p, r):
    global c
    c += r-p

def portion(mass, p, r):
    x = mass[r]
    i = p - 1
    for j in range(p, r-1):
        if  mass[j] <= x:
            i += 1
            b = mass[i]
            mass[i] = mass[j]
            mass[j] = mass[i]
    count_c(p, r - 1)
    s = mass[r]
    mass[r] = mass[i+1]
    mass[i+1] = mass[r]
    return i + 1

def quick_sort(mass, p, r):
    if p < r:
        q = portion(mass, p, r)
        quick_sort(mass, p, q - 1)
        quick_sort(mass, q + 1, r)

def main():
    mass = []
    with open("input__10000.txt", 'r') as input_file:
        n = int(input_file.readline())
        for i in range(n):
            mass.append(int(input_file.readline()))
    quick_sort(mass, 0, n-1)
    print(mass)
    print(c)


if __name__ == "__main__":
    main()