In [1]:
from random import randrange
In [2]:
pole = [randrange(10, 100) for _ in range(20)]
In [5]:
print(*pole)

19 54 30 31 82 71 74 15 60 61 50 72 40 99 89 18 32 38 49 20
In [6]:
print(pole)

[19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
In [7]:
pole = [19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
In [8]:
pole[0]
Out[8]:
19
In [9]:
pole[5]
Out[9]:
71
In [10]:
list(range(5)) #range [ako iterator] generuje cisla od 0 po parameter, list vytvori zoznam
Out[10]:
[0, 1, 2, 3, 4]
In [11]:
list(range(2, 5))
Out[11]:
[2, 3, 4]
In [13]:
for index in range(len(pole)):
    print(index, pole[index])

0 19
1 54
2 30
3 31
4 82
5 71
6 74
7 15
8 60
9 61
10 50
11 72
12 40
13 99
14 89
15 18
16 32
17 38
18 49
19 20
In [14]:
pole[-3]
Out[14]:
38
In [15]:
pole[len(pole)-3]
Out[15]:
38
In [16]:
#rez / slice
pole[2:5]
Out[16]:
[30, 31, 82]
In [17]:
pole[:5] #prvych 5
Out[17]:
[19, 54, 30, 31, 82]
In [18]:
pole[15:]
Out[18]:
[18, 32, 38, 49, 20]
In [19]:
pole[-7:] #poslednych 7
Out[19]:
[99, 89, 18, 32, 38, 49, 20]
In [20]:
pole[2:10]
Out[20]:
[30, 31, 82, 71, 74, 15, 60, 61]
In [21]:
pole[2:10:2] #od, do, krok
Out[21]:
[30, 82, 74, 60]
In [23]:
print(pole)

[19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]

Sucet¶

In [24]:
suma = 0
for index in range(len(pole)):
    suma = suma+pole[index]
print(suma)

1004
In [25]:
suma = 0
for index in range(len(pole)):
    suma += pole[index]
print(suma)

1004
In [26]:
#prechadzanie bez indexu
for prvok in pole:
    print(prvok)

19
54
30
31
82
71
74
15
60
61
50
72
40
99
89
18
32
38
49
20
In [27]:
suma = 0
for cislo in pole:
    suma += cislo
print(suma)

1004
In [28]:
sum(pole)
Out[28]:
1004

Najmensi prvok¶

In [29]:
najmensi = pole[0]
for index in range(1, len(pole)):
    if pole[index] < najmensi:
        najmensi = pole[index]
print(najmensi)

15
In [30]:
min(pole)
Out[30]:
15
In [32]:
najmensi = pole[0]
for cislo in pole[1:]:
    if cislo < najmensi:
        najmensi = cislo
print(najmensi)

15

najdenie najmensieho prvku¶

  • doplnime o zapamatanie si indexu (pozicie)
In [33]:
najmensi = pole[0]
for index in range(1, len(pole)):
    if pole[index] < najmensi:
        najmensi = pole[index]
        pozicia = index
print(najmensi, pozicia)

15 7
In [34]:
pole[7]
Out[34]:
15
In [37]:
pole = [9, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
najmensi = pole[0]
for index in range(1, len(pole)):
    if pole[index] < najmensi:
        najmensi = pole[index]
        pozicia = index
print(najmensi, pozicia)

9 7

V Jupyter notebook-u je kod interaktivny, medzi bunkami pokracuje a pamata si [inac by bola chyba, premenna pozicia neexistuje/nie je definovana]

In [35]:
najmensi = pole[0]
pozicia = 0
for index in range(1, len(pole)):
    if pole[index] < najmensi:
        najmensi = pole[index]
        pozicia = index
print(najmensi, pozicia)

15 7

Staci si pamatat poziciu ...

In [38]:
pozicia = 0
for index in range(1, len(pole)):
    if pole[index] < pole[pozicia]:
        pozicia = index
print(pole[pozicia], pozicia)

9 0
In [39]:
# index aj prvok pola
for index, prvok in enumerate(pole):
    print(index, prvok)

0 9
1 54
2 30
3 31
4 82
5 71
6 74
7 15
8 60
9 61
10 50
11 72
12 40
13 99
14 89
15 18
16 32
17 38
18 49
19 20
In [40]:
list(enumerate(pole))
Out[40]:
[(0, 9),
 (1, 54),
 (2, 30),
 (3, 31),
 (4, 82),
 (5, 71),
 (6, 74),
 (7, 15),
 (8, 60),
 (9, 61),
 (10, 50),
 (11, 72),
 (12, 40),
 (13, 99),
 (14, 89),
 (15, 18),
 (16, 32),
 (17, 38),
 (18, 49),
 (19, 20)]
In [41]:
pozicia = 0
for index, prvok in enumerate(pole):
    if prvok < pole[pozicia]:
        pozicia = index
print(pole[pozicia], pozicia)

9 0
In [42]:
for i in range(5):
    print(i) #vypise hodnoty a prejde na dalsi riadok

0
1
2
3
4
In [43]:
for i in range(5):
    print(i, end=" " ) #vypise hodnoty a medzeru

0 1 2 3 4
In [44]:
print(*pole, sep="<->") #oddelovac / separator

9<->54<->30<->31<->82<->71<->74<->15<->60<->61<->50<->72<->40<->99<->89<->18<->32<->38<->49<->20
In [47]:
for i in range(5):
    for j in range(i+1):
        print("*", end="")
    print()

*
**
***
****
*****
In [48]:
for i in range(5):
    print("*"*(i+1))

*
**
***
****
*****
In [49]:
"abc"*5
Out[49]:
'abcabcabcabcabc'

Bublinkové usporiadanie BubbleSort¶

In [52]:
print(*pole)

19 54 30 31 82 71 74 15 60 61 50 72 40 99 89 18 32 38 49 20
In [53]:
for i in range(len(pole)):
    for j in range(len(pole)):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[53], line 3
      1 for i in range(len(pole)):
      2     for j in range(len(pole)):
----> 3         if pole[j] > pole[j+1]: #porovnaj dva susedne
      4             pole[j], pole[j+1] = pole[j+1], pole[j]

IndexError: list index out of range
In [54]:
for i in range(len(pole)-1):
    for j in range(len(pole)-1):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
In [56]:
print(*pole)

15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [57]:
a, b = 2, 4 #priradi pravu stranu vlavo, prvok po prvku
In [58]:
a
Out[58]:
2
In [59]:
b
Out[59]:
4
In [60]:
print(*pole)

15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [61]:
pole[1], pole[3] = pole[3], pole[1] #vymeni druhy a stvrty prvok
print(*pole)

15 20 19 18 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [62]:
#vymena s pomocnou premennou
pomocna = pole[1]
pole[1] = pole[3]
pole[3] = pomocna
print(*pole)

15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [63]:
a, b = 2, 4
In [64]:
#vymena bez pomocnej premennej, pouzitim scitania [pozor na pretecenie mimo Pythonu, resp. pri typovanych premennych]
print(a, b)
b = a+b #a, a+b
a = b-a #b, a+b
b = b-a #b, a
print(a, b)

2 4
4 2
In [65]:
pole = [19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
In [66]:
for i in range(len(pole)-1):
    for j in range(len(pole)-1):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
    print(*pole)

19 30 31 54 71 74 15 60 61 50 72 40 82 89 18 32 38 49 20 99
19 30 31 54 71 15 60 61 50 72 40 74 82 18 32 38 49 20 89 99
19 30 31 54 15 60 61 50 71 40 72 74 18 32 38 49 20 82 89 99
19 30 31 15 54 60 50 61 40 71 72 18 32 38 49 20 74 82 89 99
19 30 15 31 54 50 60 40 61 71 18 32 38 49 20 72 74 82 89 99
19 15 30 31 50 54 40 60 61 18 32 38 49 20 71 72 74 82 89 99
15 19 30 31 50 40 54 60 18 32 38 49 20 61 71 72 74 82 89 99
15 19 30 31 40 50 54 18 32 38 49 20 60 61 71 72 74 82 89 99
15 19 30 31 40 50 18 32 38 49 20 54 60 61 71 72 74 82 89 99
15 19 30 31 40 18 32 38 49 20 50 54 60 61 71 72 74 82 89 99
15 19 30 31 18 32 38 40 20 49 50 54 60 61 71 72 74 82 89 99
15 19 30 18 31 32 38 20 40 49 50 54 60 61 71 72 74 82 89 99
15 19 18 30 31 32 20 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 31 20 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 20 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99

Vonkajsi cyklus sa vykona 19-krat, stale sa najvacsie posunie na koniec [teda poslednych 19 cisel bude na spravnej pozicii => aj to prve]

In [68]:
pole = [19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
for i in range(len(pole)-1):
    for j in range(len(pole)-1-i):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
    print(*pole[:-i], "|", *pole[-i:])

| 19 30 31 54 71 74 15 60 61 50 72 40 82 89 18 32 38 49 20 99
19 30 31 54 71 15 60 61 50 72 40 74 82 18 32 38 49 20 89 | 99
19 30 31 54 15 60 61 50 71 40 72 74 18 32 38 49 20 82 | 89 99
19 30 31 15 54 60 50 61 40 71 72 18 32 38 49 20 74 | 82 89 99
19 30 15 31 54 50 60 40 61 71 18 32 38 49 20 72 | 74 82 89 99
19 15 30 31 50 54 40 60 61 18 32 38 49 20 71 | 72 74 82 89 99
15 19 30 31 50 40 54 60 18 32 38 49 20 61 | 71 72 74 82 89 99
15 19 30 31 40 50 54 18 32 38 49 20 60 | 61 71 72 74 82 89 99
15 19 30 31 40 50 18 32 38 49 20 54 | 60 61 71 72 74 82 89 99
15 19 30 31 40 18 32 38 49 20 50 | 54 60 61 71 72 74 82 89 99
15 19 30 31 18 32 38 40 20 49 | 50 54 60 61 71 72 74 82 89 99
15 19 30 18 31 32 38 20 40 | 49 50 54 60 61 71 72 74 82 89 99
15 19 18 30 31 32 20 38 | 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 31 20 32 | 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 20 31 | 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 | 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 | 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 | 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 | 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [82]:
pole = [19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
for i in range(len(pole)-1):
    bola_vymena = False
    for j in range(len(pole)-1-i):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
            bola_vymena = True
    print(*pole[:-i], "|", *pole[-i:])
    if not bola_vymena:
        break

| 19 30 31 54 71 74 15 60 61 50 72 40 82 89 18 32 38 49 20 99
19 30 31 54 71 15 60 61 50 72 40 74 82 18 32 38 49 20 89 | 99
19 30 31 54 15 60 61 50 71 40 72 74 18 32 38 49 20 82 | 89 99
19 30 31 15 54 60 50 61 40 71 72 18 32 38 49 20 74 | 82 89 99
19 30 15 31 54 50 60 40 61 71 18 32 38 49 20 72 | 74 82 89 99
19 15 30 31 50 54 40 60 61 18 32 38 49 20 71 | 72 74 82 89 99
15 19 30 31 50 40 54 60 18 32 38 49 20 61 | 71 72 74 82 89 99
15 19 30 31 40 50 54 18 32 38 49 20 60 | 61 71 72 74 82 89 99
15 19 30 31 40 50 18 32 38 49 20 54 | 60 61 71 72 74 82 89 99
15 19 30 31 40 18 32 38 49 20 50 | 54 60 61 71 72 74 82 89 99
15 19 30 31 18 32 38 40 20 49 | 50 54 60 61 71 72 74 82 89 99
15 19 30 18 31 32 38 20 40 | 49 50 54 60 61 71 72 74 82 89 99
15 19 18 30 31 32 20 38 | 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 31 20 32 | 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 30 20 31 | 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 30 | 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 19 20 | 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [83]:
for i in range(len(pole)-1):
    bola_vymena = False
    for j in range(len(pole)-1-i):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
            bola_vymena = True
    print(*pole[:-i], "|", *pole[-i:])
    if not bola_vymena:
        break

| 15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [84]:
pole = pole[::-1]
In [85]:
print(*pole)

99 89 82 74 72 71 61 60 54 50 49 40 38 32 31 30 20 19 18 15
In [86]:
for i in range(len(pole)-1):
    bola_vymena = False
    for j in range(len(pole)-1-i):
        if pole[j] > pole[j+1]: #porovnaj dva susedne
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena
            bola_vymena = True
    print(*pole[:-i], "|", *pole[-i:])
    if not bola_vymena:
        break

| 89 82 74 72 71 61 60 54 50 49 40 38 32 31 30 20 19 18 15 99
82 74 72 71 61 60 54 50 49 40 38 32 31 30 20 19 18 15 89 | 99
74 72 71 61 60 54 50 49 40 38 32 31 30 20 19 18 15 82 | 89 99
72 71 61 60 54 50 49 40 38 32 31 30 20 19 18 15 74 | 82 89 99
71 61 60 54 50 49 40 38 32 31 30 20 19 18 15 72 | 74 82 89 99
61 60 54 50 49 40 38 32 31 30 20 19 18 15 71 | 72 74 82 89 99
60 54 50 49 40 38 32 31 30 20 19 18 15 61 | 71 72 74 82 89 99
54 50 49 40 38 32 31 30 20 19 18 15 60 | 61 71 72 74 82 89 99
50 49 40 38 32 31 30 20 19 18 15 54 | 60 61 71 72 74 82 89 99
49 40 38 32 31 30 20 19 18 15 50 | 54 60 61 71 72 74 82 89 99
40 38 32 31 30 20 19 18 15 49 | 50 54 60 61 71 72 74 82 89 99
38 32 31 30 20 19 18 15 40 | 49 50 54 60 61 71 72 74 82 89 99
32 31 30 20 19 18 15 38 | 40 49 50 54 60 61 71 72 74 82 89 99
31 30 20 19 18 15 32 | 38 40 49 50 54 60 61 71 72 74 82 89 99
30 20 19 18 15 31 | 32 38 40 49 50 54 60 61 71 72 74 82 89 99
20 19 18 15 30 | 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
19 18 15 20 | 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
18 15 19 | 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
15 18 | 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99

Počet porovnaní (časová zložitosť)?

$19+18+17+...+3+2+1=$ (sucet aritmetickej postupnosti)

$1+2+\cdots+(n-1)+n = (n+1) \cdot \frac{n}{2}$ #sucet prvy+posledny, druhy+predposledny je n+1, dvojic n/2

$\frac{n.(n+1)}{2} = \frac{n^2+n}{2} = \frac{1}{2}n^2+\frac{1}{2}n \in O\left(n^2\right)$

In [89]:
20*19//2
Out[89]:
190
In [90]:
pole = [19, 54, 30, 31, 82, 71, 74, 15, 60, 61, 50, 72, 40, 99, 89, 18, 32, 38, 49, 20]
print(*sorted(pole)) #vrati usporiadane pole

15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [91]:
print(*pole)

19 54 30 31 82 71 74 15 60 61 50 72 40 99 89 18 32 38 49 20
In [93]:
pole.sort() #usporiadaj
print(*pole)

15 18 19 20 30 31 32 38 40 49 50 54 60 61 71 72 74 82 89 99
In [ ]: