09.12.35 Stırikerfi I

Forritunarverkefni 3


Í şessu forritunarverkefni eigiğ şiğ ağ skrifa fall í 8086 smalamáli sem rağar vektor meğ hrúguröğun (heapsort). Hrúguröğun er ein af hrağvirkari röğunarağferğunum og hefur şann eiginleika ağ hún tekur nokkurn veginn jafnlangan tíma á mismunandi inntaki.

Falliğ sem şiğ skrifiğ fær í DS:SI bendi á vektor T af 16-bita orğum (ş.e. hvert stak í T er tvö bæti) og í CX gildiğ n. Falliğ rağar vektornum A[0..n] meğ hrúguröğun.

Hér ağ neğan er sauğakódi fyrir hrúguröğun. Meginhugmyndin í hrúguröğun er ağ fyrst er búin til hrúga (heap) í vektornum og síğan er sífellt tekiğ minnsta stakiğ úr hrúgunni og hún löguğ aftur.

Hrúga er tvíundartré sem hefur şann eiginleika ağ hvert foreldri er minna en bæği börn şess. Hægt er ağ setja şağ upp sem vektor, şannig ağ stak i hefur vinstra barn í staki 2*i+1 og hægra barn í 2*i+2.

            Fyrir:  T[0..n] er talnavektor
            Eftir:  T[0..n] er í hækkandi röğ
            stef HRodun(T[], n)
                fyrir k=(n-1)/2 niğur ağ 0
                    YtaNidur(T, k, n)
                fyrir k=n niğur ağ 1
                    Víxla T[0] og T[k]
                    YtaNidur(T, 0, k-1)
            endir


            Fyrir:  T[i+1..j] hefur hrúgueiginleika
            Eftir:  T[i..j] hefur hrúgueiginleika
            stef YtaNidur(T[], i, j)
                a = 2*i+1
                meğan ( a <= j )
                    ef a<j og T[a+1]>T[a] şá  a = a+1
                    ef T[i]<T[a] şá
                        Víxla T[i] og T[a]
                    i = a
                    a = 2*i+1
                endir
            endir
Şağ borgar sig fyrir ykkur ağ setja şetta upp sem tvö stef, HRodun og YtaNidur. Şiğ skuluğ ekki láta stefiğ YtaNidur breyta gildi annars viğfangsins (i), ş.e. notiğ şağ sem gildisviğfang, ekki tilvísunarviğfang.

Şiğ eigiğ líka ağ skrifa ağalforrit sem bır til 10000 staka vektor meğ slembitölum út MWC-fallinu úr Verkefni 2, og rağar honum meğ HRada. Ef şiğ viljiğ ekki byrja alltaf meğ sama sæğiğ í slembitölufallinu şá getiğ notağ ykkur ağ DOS geymir 32 bita teljara í 0040:006C, sem er hækkağur 18.2 sinnum á sekúndu.


Skiliğ útprentun şriğjudaginn 5. nóvember.

hh@rhi.hi.is, 29. október, 1996.