Rešitev (a):

Primerne predelave so:

Prej	Potem
`a[i] < a[j]` `a[i] > a[j]` `a[i] <= a[j]` `a[i] >= a[j]`	`JePred(a[i], a[j])` `JePred(a[j], a[i])` `not JePred(a[j], a[i])` `not JePred(a[i], a[j])`

Rešitev (b):

def UrejanjeZIzbiranjemP(a, JePred):
  n = len(a)
  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):
      if JePred(a[i], a[najmanjsi]):
        najmanjsi = i

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

def UrejanjeZVstavljanjemP(a, JePred):
  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 JePred(t, a[i - 1]):
      # 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.

Rešitev (c):

def JePredC(x, y):
  if x % 2 == 1:
    if y % 2 == 1:
      # liha števila so urejena padajoče
      return x > y
    else:
      # vsa liha števila so pred vsemi sodimi
      return True
  elif y % 2 == 1:
    # vsa soda števila so za vsemi lihimi
    return False
  else:
    # soda števila so urejena naraščajoče
    return x < y

Rešitev (d):

def JePredD(x, y):
  x = x.split(); y = y.split()
  # Če se x in y ujemata v priimku, ju uredimo po imenu.
  if x[1] == y[1]: return x[0] < y[0]
  # Sicer pa ju uredimo po priimku.
  else: return x[1] < y[1]

Rešitev (e):

def JePredE(x, y):
  lx = len(x); ly = len(y)
  # Če sta x in y enako dolga, ju uredimo leksikografsko.
  if lx == ly: return x < y
  # Sicer pa ju uredimo po dolžini.
  else: return lx < ly

Naloge

Doslej smo v naših postopkih urejanja primerjali elemente vhodne tabele z operatorjem <. Koristna razširitev urejanja je, da pripravimo svojo funkcijo oblike JePred(x, y), ki primerja dva elementa vhodne tabele in vrne True, če se mora x v želenem vrstnem redu uvrstiti pred y, sicer pa vrne False. Taki funkciji pravimo primerjalna funkcija ali komparator.

Postopek urejanja lahko potem predelamo, da namesto operatorja < uporablja našo primerjalno funkcijo. Na primer: iz

def Urejanje(a):
  ...
  if a[i] < a[j]: ...
  ...

nastane

def Urejanje(a, JePred):
  ...
  if JePred(a[i], a[j]): ...
  ...

Naslednji primer kaže, kako lahko s pomočjo svoje primerjalne funkcije uredimo tabelo a padajoče namesto naraščajoče:

def JeVecji(x, y):
  return x > y

a = [5, 8, 7, 2, 3]
Urejanje(a, JeVecji)
print(a) # izpiše [8, 7, 5, 3, 2]

(a) Zgoraj smo videli, kako predelati primerjavo oblike a[i] < a[j], da uporabi namesto operatorja < funkcijo JePred. Kako pa bi bilo treba predelati primerjave oblike a[i] <= a[j], a[i] > a[j] in a[i] >= a[j]?
(b) Na tu opisani način predelaj postopke za urejanje, ki smo jih predstavili v tej učni enoti (npr. UrejanjeZVstavljanjem in UrejanjeZIzbiranjem) tako, da bodo kot parameter dobili primerjalno funkcijo in jo uporabljali za primerjanje elementov vhodne tabele.
(c) Zgoraj smo videli primerjalno funkcijo JeVecji, ki poskrbi za to, da bodo elementi vhodne tabele urejeni padajoče namesto naraščajoče. Recimo pa, da želimo urejati cela števila tako, da se razvrstijo v končnem vrstnem redu najprej vsa liha števila, urejena padajoče, nato pa vsa soda števila, urejena naraščajoče. Iz tabele [5, 8, 7, 2, 3] bi pri tem vrstnem redu na primer nastala tabela [7, 5, 3, 2, 8]. Napiši primerjalno funkcijo, s katero se bo dalo urediti elemente v tem vrstnem redu.
(d) Napiši primerjalno funkcijo, s katero se bo dalo urediti tabelo nizov oblike "Ime Priimek" tako, da bodo nizi urejeni abecedno po priimkih, tisti z enakim priimkom pa abecedno po imenih. Da bo lažje, predpostavi, da so vsa imena in priimki le enobesedni in da vsebujejo le črke angleške abecede, pri čemer je prva črka imena ali priimka velika, vse ostale pa male.
(e) Napiši primerjalno funkcijo, s katero se bo dalo urediti tabelo nizov po naraščajoči dolžini, tiste z enako dolžino pa v leksikografskem vrstnem redu (to je red, ki ga na nizih dobimo že z operatorjem <).