Data-Sorting-Visualized/radixSortAlgorithm.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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
importtime

importsortingUtils
fromsortingUtilsimportwait

startTime=0

defcountingSort(array, exp1, delay):
globalstartTime
startTime=time.perf_counter()

n=len(array)

output= [0] * (n)

count= [0] * (10)

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

foriinrange(n):
index=array[i] //exp1
count[index%10] +=1
sortingUtils.selectedIndices.append(i)

foriinrange(1, 10):
count[i] +=count[i-1]

i=n-1
whilei>=0:
index=array[i] //exp1
output[count[index%10] -1] =array[i]
count[index%10] -=1
i-=1

sortingUtils.swaps+=1
sortingUtils.swapDataSound.play()
sortingUtils.selectedIndices.append(i)
wait(delay)

i=0
foriinrange(0, len(array)):
array[i] =output[i]

sortingUtils.swaps+=1
sortingUtils.swapDataSound.play()
sortingUtils.comparedIndices.append(i)
yield
wait(delay)
sortingUtils.sortTimeVisual=time.perf_counter() -startTime

defradixSort(array, delay):
max1=max(array)

exp=1
whilemax1/exp>=1:
yieldfromcountingSort(array, exp, delay)
exp*=10

defcountingSortNoVisible(array, exp1):
timeArray=array.copy()
n=len(timeArray)

output= [0] * (n)

count= [0] * (10)

foriinrange(0, n):
index=timeArray[i] //exp1
count[index%10] +=1

foriinrange(1, 10):
count[i] +=count[i-1]

i=n-1
whilei>=0:
index=timeArray[i] //exp1
output[count[index%10] -1] =timeArray[i]
count[index%10] -=1
i-=1

i=0
foriinrange(0, len(timeArray)):
timeArray[i] =output[i]

defradixSortNoVisible(array):
max1=max(array)

exp=1
whilemax1/exp>=1:
countingSortNoVisible(array, exp)
exp*=10