def mergesort(a, p, q):
mid = (p + q) // 2
k = p
r = mid + 1
while k <= mid and r <= q:
if a[k] > a[r]:
temp = a[k]
a[k] = a[r]
i = k + 1
while i <= q:
s = a[i]
a[i] = temp
temp = s
r += 1
else:
k += 1
return
def merge(a, p, q):
if p < q:
mid = (p + q) // 2
merge(a, p, mid)
merge(a, mid + 1, q)
mergesort(a, p, q)
else:
return
tab = [1, 5, 2, 4, 3, 7, 6, 9, 8]
dl = len(tab) - 1
merge(tab, 0, dl)
print(tab)
0
2
A co jest nie tak?
0
S4t napisał(a):
A co jest nie tak?
no właśnie nie chce mi posortować w sensie przestaje wywoływać się funkcja po kilku wywołaniach
0
Dodaj duuuużo printów. I może spróbuj na prostszych przypadkach - posortuj 0,1,2,3-elementową listę. Dojdziesz gdzie jest błąd :)
0
kelog napisał(a):
Dodaj duuuużo printów. I może spróbuj na prostszych przypadkach - posortuj 0,1,2,3-elementową listę. Dojdziesz gdzie jest błąd :)
Kolejne wywołania są takie, bo sprawdziłem:
merge( 0 8 )
merge( 0 4 )
merge( 0 2 )
merge( 0 1 )
merge( 0 0 )
merge( 1 1 )
mergesort( 0 1 )
merge( 2 2 )
mergesort( 0 2 )
i sie konczy na tym, a powinno sie jeszcze wywołać sporo wiecej przecież następny powinien byc już (3, 4)
3
Linijka dziesiąta to nieskończona pętla.
0
def mergesort(a, p, q):
mid = (p + q) // 2
i = p
j = mid + 1
k = 0
temp = [0] * (q - p + 1)
while i <= mid and j <= q:
if a[i] <= a[j]:
temp[k] = a[i]
i += 1
else:
temp[k] = a[j]
j += 1
k += 1
while i <= mid:
temp[k] = a[i]
i += 1
k += 1
while j <= q:
temp[k] = a[j]
j += 1
k += 1
for i in range(q - p + 1):
a[p + i] = temp[i]
def merge(a, p, q):
if p < q:
mid = (p + q) // 2
merge(a, p, mid)
merge(a, mid + 1, q)
mergesort(a, p, q)
tab = [1, 5, 2, 4, 3, 7, 6, 9, 8]
dl = len(tab) - 1
merge(tab, 0, dl)
print(tab)