Algoritmy usporiadania

Usporiadanie vkladaním (Insert Sort)

Do priebežne usporiadanej postupnosti vložíme ďalší prvok na správne miesto.

In [1]:
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
9 8 7 5 1 2 3 4 0
0 1 2 3 4 5 7 8 9

Zložitosť (časová) je kvadratická, t.j. $O(n^2)$.

Usporiadanie výberom (Selection Sort)

Vyberieme najmenší zo zostávajúcich prvkov.

In [2]:
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)
9 8 7 5 1 2 3 4 0
0 1 2 3 4 5 7 8 9

Časová zložitosť kvadratická, počet výmen lineárny.

Bublinkové usporiadanie (Bubble Sort)

In [3]:
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)
9 8 7 5 1 2 3 4 0
[8, 7, 5, 1, 2, 3, 4, 0, 9]
[7, 5, 1, 2, 3, 4, 0, 8, 9]
[5, 1, 2, 3, 4, 0, 7, 8, 9]
[1, 2, 3, 4, 0, 5, 7, 8, 9]
[1, 2, 3, 0, 4, 5, 7, 8, 9]
[1, 2, 0, 3, 4, 5, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 7, 8, 9]
0 1 2 3 4 5 7 8 9

opakujeme pokial doslo k nejakej vymene

In [4]:
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)
9 8 7 5 1 2 3 4 0
*********
0 1 2 3 4 5 7 8 9
In [5]:
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))
9 8 7 5 1 2 3 4 0
9 4 [9, 8, 7, 5, 1, 2, 3, 4, 0]
4 2 [9, 8, 7, 5]
2 1 [9, 8]
[8, 9]
2 1 [7, 5]
[5, 7]
[5, 7, 8, 9]
5 2 [1, 2, 3, 4, 0]
2 1 [1, 2]
[1, 2]
3 1 [3, 4, 0]
2 1 [4, 0]
[0, 4]
[0, 3, 4]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 7, 8, 9]

Č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)$