Tölvunarfræği 2

Vikublağ 11

Í næstu viku (ş.e. 4.-8. apríl) verğur fariğ í forgangsbiğrağir (priority queue) í kafla 9.

Forritunarverkefni 2

Falliğ qsort fylgdi upphaflega stırikerfinu Unix. Şağ er skrifağ í forritunarmálinu C og viğmót şess ber şess merki. Şağ hefur nú veriğ stağlağ og kemur nú einnig í forritasafninu stdlib.h. Şağ má sjá ágæta lısingu á fallinu og notkun şess í MSDN safninu sem fylgir meğ Visual C++ şığandanum. Einnig eru man-síğa sem fylgir Linux meğ góğa lısingu. Helsta sérkenni qsort er ağ şağ notar samanburğarfall sem şiğ şurfiğ ağ skilgreina og senda inní falliğ sem viğfang. Şetta fall hefur tvö viğföng og skilar neikvæğri tölu (t.d. -1) ef fyrra viğfangiğ er minna en şağ seinna, 0 ef viğföngin eru eins og loks skilağ şağ jákvæğri tölu ef fyrra viğfangiğ er stærra en şağ seinna. Annağ viğfang í qsort er stærğ stakanna í fylkinu í bætum. Stærğ einstakra taga er hægt ağ finna meğ sizeof fallinu.

Falliğ sort er í forritasafninu sem fylgir forritunarmálinu C++. Şetta forritasafn hét áğur STL (Standard Template Library), en er núna hluti af şví sem heitir C++ Standard Library. Til ağ nota röğunarfalliğ şarf ağ nota "#include <algorithm>". Hægt er ağ láta sort rağa venjulegum fylkjum meğ şví ağ gefa upp vistfang fyrsta staks fylkisins sem fyrra viğfangiğ og vistfangiğ fyrir aftan síğasta stakiğ sem seinna viğfangiğ. Dæmi:

   #include <algorithm>
   using namespace std;
   ...
   int a[100];
   ...
   sort( &a[0], &a[100] );
   ...

Şiğ eigiğ síğan ağ skrifa ykkar eigin röğunarfall og reyna ağ gera betur en şessi tvö kerfisföll. Líklega er sniğugast ağ byggja ykkar fall á Quicksort, en şiğ megiğ ráğa şví sjálf hvağa endurbætur şiğ geriğ á fallinu úr bókinni. Lısiğ nákvæmlega şeim endurbótum sem şiğ geriğ ef şağ er eitthvağ sem ekki kemur fyrir í kennslubókinni.

Beriğ şessi şrjú röğunarföll saman á eftirfarandi gerğum inntaks:

1. Næstum şví rağağur listi. Um 0.01% af stökunum eru ekki á réttum stağ.
2. Næstum şví í öfugri röğ. Um 0.01% af stökunum eru ekki á réttum stağ miğağ viğ öfuga röğ.
3. Ağeins 100 mismunandi gildi, sem eru jafndreifğ um listann (notiğ t.d. "a[i] = rand() % 100;").
4. Jafndreifğar slembitölur á bilinu 0 til n-1.

Şeir sem ná ağ skrifa röğunarfall sem er hrağvirkara en qsort og sort á öllum fjórum inntaksgerğunum fá aukastig fyrir şetta verkefni.