Fragment mergesortu, zwracanie listy przez funkcję

Odpowiedz Nowy wątek
2018-12-22 14:13
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?

Pozostało 580 znaków

2018-12-22 14:20
1

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


Pozostało 580 znaków

2018-12-22 14:24
0

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

edytowany 2x, ostatnio: maciej besztocha, 2018-12-22 14:25
Nie. Tak, to wina przyzwyczajeń z C:) - lion137 2018-12-22 14:26

Pozostało 580 znaków

2018-12-22 14:37
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):

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

Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)
edytowany 2x, ostatnio: superdurszlak, 2018-12-22 14:37

Pozostało 580 znaków

2018-12-22 14:48
0

Czyli w Pythonie rekurencja nie zatrzymuje się na return?

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

Pozostało 580 znaków

2018-12-22 14:56
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.

edytowany 2x, ostatnio: grski, 2018-12-22 15:00
A co z najprostszą metoda, old_1 + old_2. - enedil 2018-12-22 15:39

Pozostało 580 znaków

2018-12-22 15:02
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]
'''

Pozostało 580 znaków

2018-12-22 15:03
maciej besztocha 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

Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)

Pozostało 580 znaków

2018-12-22 15:12
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)

Warto jeszcze pamiętać o klauzuli generatorów (z yield) oraz odwrotnej iteracji (z yield from). - Guaz 2018-12-22 19:18

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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