Iskanje k-tega najmanjšega elementa

Iz MaFiRaWiki

Vsebina

Definicija problema

Podano imamo neurejeno tabelo n elementov. Iščemo k-tega najmanjšega.

Primer:

 tabela: 10, 8, 16, 7, 28, 5, 3, 13
 
 Kateri je 4. najmanjši element? 
 Odgovor: 8

Enostavni pristop

Tabelo uredimo. Potem vzamemo element na k-tem mestu v urejeni tabeli.

Na ta način pridemo do rešitve, vendar del tabele urejamo po nepotrebnem.

 Urejena tabela iz zgornjega primera: 3, 5, 7, 8, 10, 13, 16, 28
 Na 4. mestu je število 8.

Uporaba strategije deli in vladaj

Z uporabo strategijo deli in vladaj lahko problem rešimo učinkoviteje, z manjšo časovno zahtevnostjo.

Vendar enostavno deljenje tabele na polovico in iskanje rešitve v vsakem delu ne pride v poštev. Kako bi namreč potem rešitvi združili? Če bi našli na primer 4. element v levi in 4. element v desni polovici, nam to pri iskanju celotne rešitve nič ne pomaga. Četrti element v celotni tabeli je lahko čisto nek tretji element. V zgornjem primeru bi tabelo razdelili na 10, 8, 16, 7 (četrti najmanjši je 16) in 28, 5, 3, 13 (četrti najmanjši je 28).

Pomembno je, da se delitev izvede na način, ki bo pripomogel k iskanju skupne rešitve. Pri delitvi je potrebno poskrbeti, da so elementi v enem delu manjši od elementov v drugem delu. Uporabimo torej isti postopek deljenja kot pri hitrem urejanju.
Glede na velikost delov, ki jih dobimo s takšno delitvijo, potem vemo, kateri del lahko zanemarimo in v katerem delu moramo iskanje nadaljevati.
Iščemo na primer osmi najmanjši element. Z delitvijo dobimo v levem delu 10 elementov, ki so manjši od elementov v desnem delu. Iz tega vemo, da je iskani element nekje med desetimi elementi v levem delu. Če pa bi iskali na primer 12. najmanjši element, vemo da je iskani element v desnem delu.
S takšnim načinom deljenja lahko na vsaki stopnji del elementov zanemarimo in se tako izognemo nepotrebnemu urejanju.


Oglejmo si postopek podrobneje:

Tabelo n števil razdelimo glede na pivotni element p.

Slika:Iskanje_k-tega_(delitev).PNG

V levem delu je m elementov, ki so manjši ali enaki pivotu. V desnem delu pa so elementi, ki so večji ali enaki pivotu. Število elementov v desnem delu je n – m.

Če je v levem delu število elementov večje od k, vemo, da je k-ti element v tem delu. Desni del lahko zanemarimo in nadaljujemo iskanje v levem delu. Če je v levem delu na primer 10 elementov, mi pa iščemo sedmega, vemo da lahko vse elemente v desnem delu, ki so večji od elementov v levem delu, zanemarimo.

Če pa je v levem delu število elementov manjše od k, moramo nadaljevati iskanje v desnem delu. Pri tem moramo upoštevati število elementov v levem delu in v desnem delu sedaj iskati (k – m)-ti element. Če je v levem delu 5 elementov, mi pa iščemo sedmega, nadaljujemo z iskanjem 7 – 5 = drugega elementa v desnem delu.

Torej:

  • če m >= k: iščemo v levem delu k-tega najmanjšega
  • če m < k: iščemo v desnem delu (k – m)-tega najmanjšega


Primer

Podano imamo tabelo: 10, 8, 16, 7, 28, 5, 3, 13
Iščemo 4. najmanjši element.

Delimo s preurejanjem glede na pivotni element. Za pivotni element vzamemo prvega v tabeli. Dobimo:

  • levi del: 5, 8, 3, 7, 10 in desni del: 28, 16, 13

V levem delu imamo 5 elementov. Iščemo četrtega.
5 > 4 --> z iskanjem nadaljujemo v levem delu, desnega dela ne upoštevamo več.


Tabelo 5, 8, 3, 7, 10 razdelimo s preurejanjem glede na pivot 5 in dobimo:

  • levi del: 3, 5 in desni del: 8, 7, 10

V levem delu imamo sedaj 2 elementa. Iščemo četrtega.
2 < 4 --> Z iskanjem nadaljujemo v desnem delu. Levi del zanemarimo.
4 – 2 = 2 --> Iščemo 2. najmanjši element v desnem delu.


Tabelo 8, 7, 10 razdelimo s preurejanjem glede na pivotni element 8 in dobimo:

  • levi del: 7, 8 in desni del: 10

V levem delu imamo 2 elementa. Iščemo drugega.
Z iskanjem nadaljujemo v levem delu. Desni del zanemarimo.


Tabelo 7, 8 razdelimo na dva dela glede na pivotni element 7 in dobimo:

  • levi del: 7 desni del: 8

V levem delu imamo samo en element. Iščemo drugega.
Z iskanjem nadaljujejo v desnem delu, kjer je tudi samo še en element. Element 8 je torej tisti, ki ga iščemo.


Različica problema: Iskanje k-tega največjega elementa

Problem iskanja k-tega največjega elementa lahko prevedemo na iskanje K-tega najmanjšega.
K = n - k + 1

Primer:
Iščemo 5. največji element v tabeli 8 števil. Nalogo prevedemo v iskanje 4. najmanjšega elementa ( 8 - 5 + 1 = 4).

Osebna orodja