-
Notifications
You must be signed in to change notification settings - Fork 0
/
zad3.py
161 lines (133 loc) · 6.37 KB
/
zad3.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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
"""
Funkcja linearselect zwraca wartość, która znalazłaby się na k indeksie posortowanej
tablicy A.
Funkcja ta wykorzystuje funkcję median_of_medians do efektywnego wyznaczenia
przybliżonej mediany wartości obecnie sprawdzanej części tablicy (od indeksu left_idx
do indeksu right_idx), korzystając z algorytmu zwanego Magicznymi Piątkami (nie jest
konieczne korzystanie z magicznych piątek, ponieważ funkcja umożliwia wskazanie własnej
liczby elementów (jako parametr k), z których ma być wyznaczana mediana).
W kolejnym kroku, funkcja _partition, wykorzystując wyznaczoną wcześniej medianę median
jako pivot, dzieli obecnie przeszukiwaną część tablicy na 2 fragmenty. W pierwszym
fragmencie znajdą się wyłącznie wartości mniejsze od pivota, a w drugim większe lub
równe pivotowi. Funkcja zwraca funalną pozycję pivota.
Ostatnim krokiem jest sprawdzenie, czy indeks, na którym umieszczony został pivot,
jest równy indeksowi, dla którego wartość należy wyznaczyć. Jeżeli nie, konieczne
jest przeszukanie odpowiedniego fragmentu tablicy, na które została ona podzielona,
po wywołaniu funkcji _partition.
Algorytm działa w miejscu i akceptuje wielokrotne wystąpienia tej samej wartości.
"""
from random import randint, shuffle, seed
def linearselect(A, k):
if not 0 <= k < len(A):
raise IndexError(f'array index too {"small" if k < 0 else "large"}')
if len(A) == 1:
return A[0]
# Prepare variables which indicate the bounds of the subarray searched
left_idx = 0
right_idx = len(A) - 1
# Loop till the subarray is not empty
while left_idx <= right_idx:
# Calculate a median of medians and store this value on the left_idx
median_of_medians(A, left_idx, right_idx)
# Partition the current subarray using a median calculated above
# as a pivot value
pivot_idx = _partition(A, left_idx, right_idx)
# If a pivot was placed before the index desired, we have to look for
# a desired value int the right part of the current subarray
if pivot_idx < k:
left_idx = pivot_idx + 1
# If a pivot was placed after the index desired, we have to search
# for a value in the left part of the current subarray
elif pivot_idx > k:
right_idx = pivot_idx - 1
# Otherwise, (if k == pivot_idx) return a value which was searched
else:
return A[k]
def median_of_medians(arr: list, left_idx: int, right_idx: int, k: int = 5) -> 'median of medians':
"""
A function which moves a median of medians of k-element subarrays
to the left_idx of an array passed.
"""
# Store the position on which the next median will be stored
# (we will store each median of current k-element subarrays one
# after another at the beginning of the subarray which begins
# on the left_index and ends on the right_idx (inclusive)
next_swap_idx = left_idx
# Loop till the current subarray has more than k elements
while right_idx - left_idx >= k:
# Calculate and store a median of each full k-element subarray
for end_idx in range(left_idx + k-1, right_idx + 1, k):
# Store a median on the next index just after the last median stored
# (swap a median with a value placed after previously calculated medians)
_swap(arr, next_swap_idx, _select_median(arr, end_idx - k + 1, end_idx))
next_swap_idx += 1
# Calculate and store a median of the remaining subarray
# (which has less than k elements)
if end_idx < right_idx - 1:
_swap(arr, next_swap_idx, _select_median(arr, end_idx, right_idx))
next_swap_idx += 1
# Prepare variables for the next loop (we will calculate a median of
# the subarray of medians calculated above, so the right_idx will now
# be equal to the index of the last median previously determined)
right_idx = next_swap_idx - 1
next_swap_idx = left_idx
# Finally, swap a median of the subarray of medians (which has no more than
# k elements) with the first (leftmost) value of the subarray
_swap(arr, left_idx, _select_median(arr, left_idx, right_idx))
# Return a value of a median
return arr[left_idx]
def _select_median(arr: list, left_idx: int, right_idx: int) -> int:
"""
A function which sorts a part of a subarray delimited by
the left_idx and the right_idx and returns an index of a median.
"""
# Using the Selection Sort concept, sort only elements of the
# subarray which are placed up to the middle index (including
# the middle element)
mid_idx = (right_idx + left_idx) // 2
for i in range(left_idx, mid_idx + 1):
min_idx = i
for j in range(i + 1, right_idx + 1):
if arr[j] < arr[min_idx]:
min_idx = j
_swap(arr, min_idx, i)
# Return the middle index which is a position of the median
# after sorting a part of the subarray
return mid_idx
def _swap(arr: list, i: int, j: int):
"""
A helper function which swaps elements of an array
"""
arr[i], arr[j] = arr[j], arr[i]
def _partition(arr: list, left_idx: int, right_idx: int) -> int:
"""
A function which partitions a subarray (part of the input array from the
left_idx to the right_idx) into elements greater than or equal to the pivot
element (the leftmost value of a subarray) and lower than a pivot.
This function returns a final position of the pivot value in the sorted array
(a position on which a pivot will be placed after sorting the input array).
"""
# After running the median of medians function a pivot (this median of medians)
# will be placed on the left_idx of the subarray
pivot = arr[left_idx]
# Partition an array into 2 subarrays: the first one of elements lower than
# a pivot and the second one of elements greater than or equal to a pivot
i = left_idx + 1
for j in range(left_idx, right_idx + 1):
if arr[j] < pivot:
_swap(arr, i, j)
i += 1
# Place a pivot element on its destination index
_swap(arr, i - 1, left_idx)
return i - 1 # Return a pivot position after the last swap
seed(42)
n = 11
for i in range(n):
A = list(range(n))
shuffle(A)
print(A)
x = linearselect(A, i)
if x != i:
print("Blad podczas wyszukiwania liczby", i)
exit(0)
print("OK")