-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsort.py
41 lines (34 loc) · 1010 Bytes
/
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
def heapsort(alist):
build_max_heap(alist)
for i in range(len(alist) - 1, 0, -1):
alist[0], alist[i] = alist[i], alist[0]
max_heapify(alist, index=0, size=i)
def parent(i):
return (i - 1)//2
def left(i):
return 2*i + 1
def right(i):
return 2*i + 2
def build_max_heap(alist):
length = len(alist)
start = parent(length - 1)
while start >= 0:
max_heapify(alist, index=start, size=length)
start = start - 1
def max_heapify(alist, index, size):
l = left(index)
r = right(index)
if (l < size and alist[l] > alist[index]):
largest = l
else:
largest = index
if (r < size and alist[r] > alist[largest]):
largest = r
if (largest != index):
alist[largest], alist[index] = alist[index], alist[largest]
max_heapify(alist, largest, size)
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
heapsort(alist)
print('Sorted list: ', end='')
print(blist)