Urejanje z zlivanjem

x
 
1
def ZlijZaporedji(a, b):
2
  c = [] # to bo naše izhodno zaporedje
3
  # dolžina vhodnih zaporedij
4
  n = len(a); m = len(b)
5
  # koliko elementov iz a oz. b smo že premaknili
6
  # v zaporedje c
7
  i = 0; j = 0
8
  while i < n or j < m:
9
    if j >= m: # zaporedje b smo že izpraznili,
10
               # naslednji element vzemimo iz a
11
      c.append(a[i]); i += 1
12
    elif i >= n: # zaporedje a smo že izpraznili,
13
                 # naslednji element vzemimo iz b
14
      c.append(b[j]); j += 1
15
    elif a[i] < b[j]:
16
      c.append(a[i]); i += 1
17
    else:
18
      c.append(b[j]); j += 1
19
  return c
20
21
a = [5, 6, 8, 10]
22
b = [1, 3, 7, 9]
23
print(ZlijZaporedji(a, b))

Izvedi Počisti



V vsaki iteraciji zanke while premaknemo en element iz enega od vhodnih zaporedij v izhodno zaporedje. Skupaj se torej izvede n + m iteracij te zanke, če sta n in m dolžini vhodnih zaporedij. V vsaki iteraciji imamo največ eno primerjanje dveh elementov (a[i] in b[j]) ter eno dodajanje na konec izhodnega zaporedja c. Časovna zahtevnost tega postopka je torej O(n + m).

Vaja