Do priebežne usporiadanej postupnosti vložíme ďalší prvok na správne miesto.
pole = [int(_) for _ in input().split()]
n = len(pole)
for i in range(1, n):
#vlozime i-ty prvok na svoje miesto
j = i-1
prvok = pole[i]
while j >= 0 and pole[j] > prvok:#posuvame sa dolava, kym su vacsie cisla alebo sme na zaciatku postupnosti
pole[j+1] = pole[j]
j -= 1 #chod dolava
j += 1
pole[j] = prvok
print(*pole) #vypise usporiadany zoznam cisel
Zložitosť (časová) je kvadratická, t.j. $O(n^2)$.
Vyberieme najmenší zo zostávajúcich prvkov.
pole = [int(_) for _ in input().split()]
n = len(pole)
for i in range(n-1): #najdeme i-ty najmensi prvok
ind_min = i
for j in range(i+1, n):
if pole[j] < pole[ind_min]: #nasli sme mensi prvok
ind_min = j
pole[i], pole[ind_min] = pole[ind_min], pole[i] #vymenime dva prvky
print(*pole)
Časová zložitosť kvadratická, počet výmen lineárny.
pole = [int(_) for _ in input().split()]
n = len(pole)
for i in range(n-1):
for j in range(n-1-i): #moze byt aj n-1
if pole[j] > pole[j+1]:
pole[j], pole[j+1] = pole[j+1], pole[j] #vymen dva susedne prvky
print(pole)
print(*pole)
opakujeme pokial doslo k nejakej vymene
pole = [int(_) for _ in input().split()]
n = len(pole)
bola_vymena = True
while bola_vymena:
print('*',end='') #za kazdy jeden prechod vypiseme hviezdicku
bola_vymena = False
for j in range(n-1):
if pole[j] > pole[j+1]:
pole[j], pole[j+1] = pole[j+1], pole[j] #vymen dva susedne prvky
bola_vymena = True
print() #prechod na dalsi riadok
print(*pole)
pole = [int(_) for _ in input().split()]
n = len(pole)
def spajanim(p): #usporiadaj spajanim pole p
#rozdelime na 2 polovice
pocet = len(p)
if pocet < 2:
return p
index = pocet // 2
print(pocet, index, p)
#rekurzivne spocitame obe polovice
lava = spajanim(p[:index])
prava = spajanim(p[index:])
#spojime usporiadane polovice
i, j = 0, 0
vysl = []
while i < len(lava) and j < len(prava): #ak este ziadna nie je na konci, tak porovname 2 prvky
if lava[i] > prava[j]:
vysl.append(prava[j])
j += 1
else:
vysl.append(lava[i])
i += 1
while i < len(lava):#vypiseme zvysok lavej casti
vysl.append(lava[i])
i += 1
while j < len(prava): #vypiseme zvysok pravej casti
vysl.append(prava[j])
j += 1
print(vysl) #priebezne usporiadane
return vysl
print(spajanim(pole))
Časovú zložitosť môžeme vypočítať z rekurentného vzťahu $T\left(n\right) = 2T\left(\frac{n}{2}\right)+n$ pomocou Hlavnej vety (Master Theorem)), $T(n) = \theta\left(n . \log n\right)$