Fragment mergesortu, zwracanie listy przez funkcję

0
def msort(li):
	if len(li)>1:
		if (len(li)%2)==0:
			p=int(len(li)/2)
		else:
			p=int(((len(li))-1)/2)
			
		print(li)
		print(li[:p])
		print(li[p:])
		print('wwww')
		
		msort(li[:p])
		msort(li[p:])
	return li
	
#main			

li= [4,2,6,3]

print (li)
print ('aaaa')
li=msort(li)	
print('xxxx')
print (li)

Chciałbym się zapytać dlaczego funkcja nie zwraca tylko pierwszego elementu listy (tutaj 4) lecz zwraca ją całą? Nie jest tak że, po dotarciu do return funkcja zwraca to co pod nim było?

1

Bo Zwracasz całą listę: return li, return li[0] zwróci pierwszy element. A w ogóle, to ten mergesort nie działa.

0

To jest tylko fragment mergesorta. Poza tym czy nie powinna być tu zwracana lista jednoelementowa?
Może to wina przyzwyczajeń z C.

1

W Pythonie gdy utworzysz sobie listę:

li = [1, 2, 3, 4]

to li będzie referencją do obiektu, który jest listą, z którego możesz wyciągać elementy, wywoływać jego metody (np. li.append(5)) czy wywoływać na nim funkcje (len(li)) :) li nie jest wskaźnikiem na pierwszy element tablicy ;)

if (len(li)%2)==0:
p=int(len(li)/2)
else:
p=int(((len(li))-1)/2)


To możesz uprościć, stosując trochę inny operator dzielenia (floor division):

```python
 p = len(li) // 2 # z automatu zaokrągli w dół do liczby całkowitej
0

Czyli w Pythonie rekurencja nie zatrzymuje się na return?

W jaki sposób on później scala jednoelementowe listy?

1

Rekruencja w Pythonie działa normalnie, tak jak i w innych językach.

Jak scalane są listy jednoelementowe? Można zrobić to na dwa sposoby - albo utworzyć nową listę i rozpakować do niej dwie poprzednie, czyli np.

old_1 = [1]
old_2 = [2]
new_llist = []
new_list.extend(old_1)
new_list.extend(old_2)

Lub

old_1 = [1]
old_2 = [2]
new_llist = []
new_list.append(old_1[0])
new_list.append(old_2[0])

lub też

old_1 = [1]
old_2 = [2]
new_list = [*old_1, *old_2]

Druga rzecz, jaką warto wspomnieć, to przekazywanie argumentów.

Domyślnie mamy dwie metody przekazywania argumentów w funkcji w Pythonie - by reference i by value.
Rzeczy, które są immutable, w Pythonie lecą by value, czyli dostajesz tą skopiowaną wartość - standardowe zachowanie np. z C itd.. W innym wypadku przekazywana jest referencja. Czyli w przypadku list, masz takie jakby wskaźniki z C, czyli jeśli przekażesz listę jako argument do funkcji, zmodyfikujesz ją, to po wyjściu z funkcji, oryginalna lista będzie zmodyfikowana.

1

Mergesort, Możesz sobie porównać:

def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1


alist1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(alist1)
print(alist1)

'''
output -> [17, 20, 26, 31, 44, 54, 55, 77, 93]
'''
3
konto usunięte napisał(a):

Czyli w Pythonie rekurencja nie zatrzymuje się na return?

W Pythonie, jak w chyba każdym innym języku, jeżeli wywołasz funkcję, która wywoła samą siebie, musisz najpierw wrócić z wewnętrznego wywołania, by móc wrócić z zewnętrznego.

def FOO():
  # cośtam cośtam, nieistotne
  if warunek:
    FOO()
  return wynik

Wykona się mniej więcej w ten sposób:

WYWOŁANIE FOO (1-sze)
 * WYKONANIE FOO (1-szego)
 * WYWOŁANIE FOO (2-gie, rekurencyjne)
 *  * WYKONANIE FOO (2-giego)
 [...]
 *  *  * WYWOŁANIE FOO (N-te, rekurencyjnie)
 *  *  *  * WYKONANIE FOO (N-tego)
 *  *  *  * POWRÓT Z FOO (N-tego)
 *  *  * POWRÓT Z FOO (N-1 - szego)
 [...]
 *  * POWRÓT Z FOO (2-giego)
 * POWRÓT Z FOO (1-szego)

W jaki sposób on później scala jednoelementowe listy?

Kto? mergesort? Mniej więcej w ten sposób:

lewa = mergesort(lista[:p])
prawa = mergesort(lista[p:])
posortowana = []
while len(lewa) > 0 and len(prawa) > 0:
  if lewa[0] > prawa [0]:
    posortowana.append(lewa.pop(0))
  else:
    posortowana.append(prawa.pop(0))
  # Jeśli któraś nie jest pusta, dorzuci ją na koniec
  posortowana = posortowana + lewa + prawa
  return posortowana
0

Rekurencja w Pythonie niczym się nie różni od innych języków:

def rec_fun(arg):
    if cond: return <something>
    else: return F(rec_fun(g(arg)))

Przykład, suma liczb do n:

def a_sum(n):
	if n == 0: 
		return 0;
	else: 
		return n + a_sum(n - 1)

1 użytkowników online, w tym zalogowanych: 0, gości: 1