To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:

priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.

Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.

Rešitev (a):

def UrejanjeZVstavljanjem2(a):
  n = len(a)
  for k in range(1, n):
    # Urejeni del tabele je a[0:k], neurejeni del pa a[k:n]. Vstavimo
    # element a[k] v urejeni del tabele.
    t = a[k] # Zapomnimo si element, ki ga bomo vstavljali
    i = k # Indeks i označuje "prazno mesto" ob vstavljanju

    while i > 0 and a[i - 1] > t:
      # Element a[i - 1] je večji od t-ja, ki ga vstavljamo zato
      # premaknimo a[i - 1] za eno mesto naprej.
      a[i] = a[i - 1]
      i = i - 1 # Mesto i - 1 je zaradi tega premika zdaj prazno.

    a[i] = t # Vstavimo element t na prazno mesto.

    # Izpišimo tabelo
    l = ", ".join(str(x) for x in a[:k + 1])
    d = ", ".join(str(x) for x in a[k + 1:])
    print("[" + l + "|" + d + "]")

Rešitev (c): Ocenjena časovna zahtevnost funkcije je O(n²).

Rešitev (d): Čas urejanja z vstavljanjem je zelo odvisen od začetnega stanja tabele. Če je tabela že pravilno urejena, je urejanje z vstavljanjem zelo hitro - O(n) namesto O(n²). Najpočasnejše je, če je urejena ravno narobe (padajoče namesto naraščajoče). Pri naključno premešani tabeli je čas urejanja približno polovico njenega najslabšega možnega.

Rešitev (a):

def UrejanjeZIzbiranjem5(a):
  n = len(a)
  stPrimerjav = 0; stPrireditev = 0

  for k in range(n):
    # Urejeni del tabele je a[0:k], neurejeni del pa a[k:n]. Poiščimo
    # najmanjši element v neurejenem delu.
    najmanjsi = k

    for i in range(k + 1, n):
      stPrimerjav += 1 # primerjava v naslednji vrstici
      if a[i] < a[najmanjsi]:
        najmanjsi = i

    # Zamenjajmo elementa na indeksih k in najmanjsi.
    t = a[k]
    a[k] = a[najmanjsi]
    a[najmanjsi] = t

    stPrireditev += 3 # tri prireditve v prejšnjih vrsticah

  return [stPrimerjav, stPrireditev]


def UrejanjeZVstavljanjem3(a):
  n = len(a)
  stPrimerjav = 0; stPrireditev = 0

  for k in range(1, n):
    # Urejeni del tabele je a[0:k], neurejeni del pa a[k:n]. Vstavimo
    # element a[k] v urejeni del tabele.
    t = a[k] # Zapomnimo si element, ki ga bomo vstavljali
    i = k # Indeks i označuje "prazno mesto" ob vstavljanju.

    while i > 0:
      stPrimerjav += 1
      if not (a[i - 1] > t): break
      # Element a[i - 1] je večji od t-ja, ki ga vstavljamo zato
      # premaknimo a[i - 1] za eno mesto naprej.
      a[i] = a[i - 1]; stPrireditev += 1
      i = i - 1 # Mesto i - 1 je zaradi tega premika zdaj prazno.

    # Vstavimo element t na prazno mesto.
    a[i] = t; stPrireditev += 1

  return [stPrimerjav, stPrireditev]

Rešitev (b):

Urejanje z izbiranjem:

• vidimo, da izvede O(n²) primerjav in O(n) prireditev;
• vidimo, da je število primerjav in prireditev odvisno le od dolžine tabele, ne pa od njenega začetnega stanja.

Urejanje z vstavljanjem:

• vidimo, da izvede O(n²) primerjav in O(n²) prireditev, vedno približno enako obojih;
• vidimo, da je število primerjav in prireditev zelo odvisno ne le od dolžine tabele, ampak tudi od njenega začetnega stanja; če je tabela že na začetku urejena naraščajoče, imamo le O(n) primerjav in prireditev; največ jih je, če je urejena padajoče; pri naključno premešanih tabelah pa je približno pol manj primerjav in prireditev kot v tem najslabšem primeru.