Urejanje

Urejanje je problem, kako prerazporediti elemente nekega zaporedja tako, da bodo razvrščeni po nekem želenem vrstnem redu. Nize na primer pogosto želimo urediti po abecedi, števila po velikosti (od manjših proti večjim ali pa obratno) in podobno. To pride pogosto prav, na primer za lepši izpis rezultatov, včasih pa je tudi del katerega drugega postopka.

Primer

Operater neke kino dvorane ima na izbiro n filmov različne dolžine; i-ti film (za i = 0, 1, ..., n - 1) je dolg t_i minut. Iz teh filmov bi rad sestavil spored za filmski maraton, ki bo trajal D minut. Izbrati hoče čim več filmov, vendar tako, da njihova skupna dolžina ne bo presegla D. Posamezni film lahko izbere največ enkrat. Katere filme naj izbere?

Pri tem problemu se na primer izkaže, da dobimo najboljšo rešitev tako, da filme pregledujemo od najkrajših proti daljšim in jih dodajamo v naš spored, dokler je pač mogoče (torej dokler ne bi presegli skupne dolžine D). Tu je torej prvi korak rešitve ta, da filme uredimo po dolžini.

V tej učni enoti bomo predpostavili, da lahko elemente našega zaporedja primerjamo z operatorjem < in da jih želimo urediti od manjših proti večjim. Enake postopke lahko potem seveda uporabimo tudi za poljuben drug vrstni red, če za primerjanje elementov namesto operatorja < uporabimo kaj drugega.

V splošnem si torej lahko postopke za urejanje razlagamo tako, da v njih primerjava »x < y« ne pomeni »x je manjši od y«, pač pa »v vrstnem redu, po katerem želimo urediti naše zaporedje, mora x nastopiti prej kot y«.

Znanih je veliko postopkov za urejanje, od preprostih in počasnejših do bolj zapletenih in učinkovitejših.

Vaja

Pomagaj operaterju kino dvorane razvrstiti filme od najkrajšega do najdaljšega.

Avatar (162 min)
Titanic (194 min)
The Avengers (144 min)
Frozen (102 min)
Iron Man 3 (130 min)
Skyfall (143 min)

Povleci in spusti gradnik	Film 1
	Film 2
	Film 3
	Film 4
	Film 5
	Film 6