Data-Sorting-Visualized/quickSortAlgorithm.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
importtime

importsortingUtils
fromsortingUtilsimportwait

startTime=0

defpartition(array, low, high, delay):
globalstartTime
iflow==0andhigh==len(array) -1:
startTime=time.perf_counter()

pivot=array[high]
i=low-1

sortingUtils.selectedIndices= [high]

forjinrange(low, high):
sortingUtils.comparisons+=1

sortingUtils.comparedIndices= [j, high]

ifarray[j] <pivot:
i+=1
sortingUtils.comparedIndices= [i, j]
array[i], array[j] =array[j], array[i]
sortingUtils.swapDataSound.play()
sortingUtils.swaps+=1
sortingUtils.sortTimeVisual=time.perf_counter() -startTime
yield
wait(delay)

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

array[i+1], array[high] =array[high], array[i+1]

iflow==0andhigh==len(array) -1:
sortingUtils.sortTimeVisual=time.perf_counter() -startTime

returni+1

defquickSort(array, low, high, delay):
globalstartTime

iflow<high:
part=yieldfrompartition(array, low, high, delay)

yieldfromquickSort(array, low, part-1, delay)
yieldfromquickSort(array, part+1, high, delay)

defpartitionNoVisible(array, low, high):
pivot=array[high]
i=low-1

forjinrange(low, high):
ifarray[j] <pivot:
i+=1
array[i], array[j] =array[j], array[i]

array[i+1], array[high] =array[high], array[i+1]

returni+1

defquickSortNoVisible(array, low, high):
timeArray=array.copy()
iflow<high:
part=partitionNoVisible(timeArray, low, high)

quickSortNoVisible(timeArray, low, part-1)
quickSortNoVisible(timeArray, part+1, high)