Diskuze: Třídící algoritm "Insertion sort" v Pythonu

Alexandr Saveljev

Člen

Alexandr Saveljev:8.9.2023 12:18

V diskuzi "Funkce v Pythonu. Musí něco vrátit." vzniklo nové vlákno a rozhodl jsem se ho přesunout do samostatného vlákna.
Možná má někdo stejné problémy s porozuměním jako já.
Takže máme kód:

def insertionSort(zadanePole):               # uživatel zadává čísla:  95, 2, -5, 7, 0
    i = 0
    klic = 0
    j = 0
    for i in range(1, len(zadanePole), 1):
        klic = zadanePole[i]
        j = i - 1
        while (j >= 0 and zadanePole[j] > klic ):
            zadanePole[j + 1] = zadanePole[j]
            j = j - 1
        zadanePole[j + 1] = klic

cisla = input("Zadej čísla pro seřazení (oddělená čárkou): ")
vstupniPole = [int(n) for n in cisla.split(",")]
insertionSort(vstupniPole)
print("Seřazená čísla:")
print(*vstupniPole, sep=', ')

V tomto kódu do:

zadanePole[j + 1] = zadanePole[j]

je všechno jasně.
Co NENÍ jasně, je:

    j = j - 1
zadanePole[j + 1] = klic

Rozumím, že j = j - 1 je řidicí příkaz pro zadanePole[j] , tady je číslo 2 , kterému po změně místa je třeba najít
správnou pozici v seřazené části pole nalevo od řazeného prvku, tady číslo 95.
Zatim co tam je jen jedno místo, a pak čisté pole, 2 vložime před 95.
To je jasně. Co NENÍ jasně, je: - kde je řidicí příkaz pro takový postup?
Jak PY pochopí, že chci číslo 2 porovnat se všemi čísly vlevo od 95 poté, co si vyměnili místa?
Proč všechna čísla nevynásobit nebo nevydělit?
Rozumím, že po první iterace vlevo od 95 bude pouze jedno číslo.
Ale po druhém cyklu vlevo od 95 již budou dvě čísla, a tak dále.
ŽÁDÁM o odpověď jen na tuto otázku, že jsem jen začátečník, a je mi těžké pochopit všechno ihněd.
Další otázky, ohledně zadanePole[j + 1] = klic, probereme pozdě.

Zkusil jsem: Měl jsem dlouhou diskuzi ve vlákně "Funkce v Pythonu. Musí něco vrátit.".
Hodně jsem pochopil.

Chci docílit: Potřebuji sám sobě vysvětlit a pochopit poslední dvě otázky.

Odpovědět

8.9.2023 12:18

DarkCoder

Člen

DarkCoder:8.9.2023 12:44

Odpověď na smysl posledních dvou příkazů v Insertion Sortu najdeš v mém posledním příspěvku ve tvém vlákně: "Funkce v Pythonu. Musí něco vrátit."

Nahoru Odpovědět

8.9.2023 12:44

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Alexandr Saveljev

Člen

Alexandr Saveljev:8.9.2023 14:53

Ano, už jsem to chapu.
Problemem bylo to, že probiral jsem kód od začátku. Ale je lepší to udělat, když vezmeš druhou a třetí iteraci.
V tomto případě máš dvě čísla v seřazeném poli, a je lěpší pochopit co a jak jde.

# první iterace se skončia a nová začíná. "zadanePole" vypádá takto:  2, 95, -5, 7, 0
for i in range(1, len(zadanePole), 1):   # for 2 in range[1, 2, 3, 4]
    klic = zadanePole[i]                         # klic = -5
    j = i - 1                                            # j = 2 - 1 = 1
    while (j >= 0 and zadanePole[j] > klic ):  # while (1 >= 0 and 95 > -5 ):
            zadanePole[j + 1] = zadanePole[j]  # -5 se měni místo s číslem 95
            j = j - 1     # tak jako "while" je stále Troo, cyklus while pokračuje, ale "j" při tomto = j - 1,, tj.
# while (0>=0 and 2 > -5): 2 se měni místo s číslem -5, a "zadanePole" vypádá takto:  -5, 2, 95, 7, 0
# tak jako "while" je stále Troo, cyklus "while" pokračuje, ale "j" při tomto = j - 1,, tj. ...  - a tady je prazdné pole, tj, while = False
#iterace se skončila, "zadanePole" vypádá takto:  -5, 2, 95, 7, 0
# začíná nová iterace "for", tj.
# for 3 in in range[1, 2, 3, 4]
    klic = zadanePole[i]                    # klic = 7
    j = i - 1                                     # j = 3 - 1 = 2,   tj. je 95
    while (j >= 0 and zadanePole[j] > klic ):  # while (2 >= 0 and 95 > 7 ):
        zadanePole[j + 1] = zadanePole[j]     # 7 se měni místo s číslem 95
         j = j - 1     # tak jako "while" je stále Troo, cyklus "while" pokračuje, ale "j" při tomto = j - 1,, tj.
# while (1>=0 and 2 > 7): while = False, iterace se skončila, 2 se neměni místo s číslem 7,
#a "zadanePole" vypádá takto:  -5, 2, 7, 95, 0
#iterace se skončila, "zadanePole" vypádá takto:  -5, 2, 7, 95, 0
    # začíná nová iterace "for", tj.
    # for 4 in in range[1, 2, 3, 4]
    ...
        zadanePole[j + 1] = klic

Nahoru Odpovědět

8.9.2023 14:53

Alexandr Saveljev

Člen

Alexandr Saveljev:8.9.2023 14:59

Tj. tata otázka byla s Tvou pomocí vyřešena!
Velmi dobře.
Teď to chápu, a to je hlavní!

Nahoru Odpovědět

8.9.2023 14:59

DarkCoder

Člen

DarkCoder:8.9.2023 15:42

Ale je lepší to udělat, když vezmeš druhou a třetí iteraci. V tomto případě máš dvě čísla v seřazeném poli, a je lěpší pochopit co a jak jde.

Samozřejmě, musíš projít celý algoritmus a nekončit jednou iterací.

Jinak je třeba chápat, že příkaz:

zadanePole[j + 1] = zadanePole[j]

Ve skutečnosti nepředstavuje přesun ale kopírování. Každý prvek má hodnotu. Buď validní nebo odpad. To že jsme mluvili o přesunu pomáhá porozumět algoritmu. Je však třeba brát v potaz, že v reálu je to kopírování.

Jinak mě pobavilo používání slova Troo pro logickou pravdu True. :-)

Nahoru Odpovědět

8.9.2023 15:42

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Alexandr Saveljev

Člen

Alexandr Saveljev:8.9.2023 16:13

Ano, specham, a odsud i "Troo".
Omlouvám se!
Nevím, proč mi trvalo tak dlouho, než jsem přišel na to, že uvnitř iterace "for" funguje cyklus "while".
Ohledně Je však třeba brát v potaz, že v reálu je to kopírování. - jaký je rozdil?
Jasně, že se mění není idexy, ale hodnoty. Tak jaký je v tom rozdíl?
Nevytváříme novou proměnnou k uložení a následné výměně těchto hodnot, že?
Poraď, prosím.

Nahoru Odpovědět

8.9.2023 16:13

DarkCoder

Člen

DarkCoder:8.9.2023 17:37

Nemusíš se omlouvat. Vizuální vyjádření není podstatné, hlavní je význam a ten byl správný. Pobavilo to, nic negativního v tom nebylo.

Index je ordinarni hodnota která slouží pro přístup k prvku kde je uložena hodnota.

Přesun je, když původní lokace bude na nové lokaci a na Původní nebude nic. Což v programovani je nemyslitelné.

Kopírování je, když Původní lokace bude na nové lokaci a zároveň zůstane i na staré lokaci. To je prostě přiřazení.

a = b je přiřazení, a obsahuje totéž co b. b je na Původní i nové lokaci. Můžeš to tedy brát i jako Kopírování.

Přesun si můžeš představit jako váleček s heliem. Když ho pustit, mění lokaci, ale na Původní pozici nic není.

Nahoru Odpovědět

8.9.2023 17:37

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Nejčastěji vyhledáváné

Diskuze: Třídící algoritm "Insertion sort" v Pythonu