Urejanje z vstavljanjem

Vaja


Zapišimo postopek urejanja z vstavljanjem še v pythonu:

x
 
1
def UrejanjeZVstavljanjem(a):
2
  n = len(a)
3
  for k in range(1, n):
4
    # Urejeni del tabele je a[0:k], neurejeni
5
    # del pa a[k:n]. Vstavimo element a[k] v
6
    # urejeni del tabele.
7
    # Zapomnimo si element, ki ga bomo vstavljali
8
    t = a[k]
9
    # Indeks i označuje "prazno mesto" ob
10
    # vstavljanju
11
    i = k
12
    while i > 0 and a[i - 1] > t:
13
      # Element a[i - 1] je večji od t-ja, ki ga
14
      # vstavljamo; zato premaknimo a[i - 1] za
15
      # eno mesto naprej
16
      a[i] = a[i - 1]
17
      # Mesto i - 1 je zaradi tega premika zdaj
18
      # prazno
19
      i = i - 1
20
    # Vstavimo element t na prazno mesto
21
    a[i] = t
22
23
tabela = [13, 4, 9, 21, 67, 33, 59, 43]
24
print(tabela)
25
UrejanjeZVstavljanjem(tabela)
26
print(tabela)

Izvedi Počisti