-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.py
78 lines (63 loc) · 2.56 KB
/
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
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
from visualizer import SortVisualizer
class QuickSort(SortVisualizer):
"""
QuickSort class that extends the SortVisualizer class to visualize the quick sort algorithm.
Attributes:
data (list): A list of integers to be sorted.
"""
def __init__(self, data):
"""
Constructor for the QuickSort class.
Args:
data (list): A list of integers to be sorted.
"""
super().__init__(data)
def sort(self):
"""
Public method to initiate the quick sort algorithm.
"""
self._quicksort(0, len(self.data) - 1)
def _quicksort(self, low, high):
"""
Private recursive method to perform the quick sort.
Args:
low (int): Starting index of the segment to be sorted.
high (int): Ending index of the segment to be sorted.
"""
if low < high:
pivot_index = self._partition(low, high)
self._quicksort(low, pivot_index)
self._quicksort(pivot_index + 1, high)
def _partition(self, low, high):
"""
Private method to partition the segment of the list using the pivot.
Elements smaller than the pivot will be on the left, and elements greater than the pivot will be on the right.
Args:
low (int): Starting index of the segment to be partitioned.
high (int): Ending index of the segment to be partitioned.
Returns:
int: The index position of the pivot after partitioning.
"""
pivot = self.data[low]
left = low + 1
right = high
done = False
while not done:
# Increment 'left' index while the element at 'left' is less than the pivot
while left <= right and self.data[left] <= pivot:
left = left + 1
self.update()
# Decrement 'right' index while the element at 'right' is greater than the pivot
while self.data[right] >= pivot and right >= left:
right = right - 1
self.update()
# If there is an element larger on the left of the pivot and an element smaller on the right, swap them
if right < left:
done = True
else:
self.data[left], self.data[right] = self.data[right], self.data[left]
self.update(left, right)
# Swap the pivot with the element at the 'right' index
self.data[low], self.data[right] = self.data[right], self.data[low]
self.update(low, right)
return right