Data-Sorting-Visualized/heapSortAlgorithm.py at main · PyricRL/Data-Sorting-Visualized · 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
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
importtime

importsortingUtils
fromsortingUtilsimportwait

startTime=0

defheapify(array, n, i, delay):
largest=i
l=2*i+1
r=2*i+2

sortingUtils.selectedIndices.clear()
sortingUtils.comparedIndices.clear()

sortingUtils.selectedIndices.append(largest)

ifl<nandarray[l] >array[largest]:
largest=l
sortingUtils.selectedIndices.append(largest)

ifr<nandarray[r] >array[largest]:
largest=r
sortingUtils.selectedIndices.append(largest)

sortingUtils.comparisons+=1

iflargest!=i:
sortingUtils.comparedIndices.append(i)
sortingUtils.swaps+=1
array[i], array[largest] =array[largest], array[i]
yieldfromheapify(array, n, largest, delay)
sortingUtils.sortTimeVisual=time.perf_counter() -startTime
yield
wait(delay)

defheapSort(array, delay):
globalstartTime
startTime=time.perf_counter()
n=len(array)

foriinrange(n//2-1, -1, -1):
yieldfromheapify(array, n, i, delay)

foriinrange(n-1, 0, -1):
array[0], array[i] =array[i], array[0]
sortingUtils.swaps+=1
yieldfromheapify(array, i, 0, delay)

defheapifyNoVisible(array, n, i):
largest=i
l=2*i+1
r=2*i+2

ifl<nandarray[l] >array[largest]:
largest=l

ifr<nandarray[r] >array[largest]:
largest=r

iflargest!=i:
array[i], array[largest] =array[largest], array[i]
heapifyNoVisible(array, n, largest)

defheapSortNoVisible(array):
startTime=time.perf_counter()
timeArray=array.copy()
n=len(timeArray)

foriinrange(n//2-1, -1, -1):
heapifyNoVisible(timeArray, n, i)

foriinrange(n-1, 0, -1):
timeArray[0], timeArray[i] =timeArray[i], timeArray[0]
heapifyNoVisible(timeArray, i, 0)

sortingUtils.sortTime=time.perf_counter() -startTime