Tölvunarfræği 2

Vikublağ 11


Í síğustu viku var byrjağ ağ fjalla um röğunarağferğina Quicksort, sem er í kafla 7. Í şessari viku, sem reyndar er klofin í tvennt af páskunum, verğur rætt nánar um Quicksort og ımsar útgáfur af henni sem laga vandamál viğ Quicksort á tilteknum gerğum inntaka.

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

Forritunarverkefni 2

Í şessu öğru forritunarverkefni eigiğ şiğ ağ skoğa şau röğunarföll sem fylgja meğ stırikerfunum Windows og Linux og forritunarmálinu C++. Şiğ eigiğ ağ bera şau saman á nokkrum mismunandi gerğum inntaks og athuga hvort şiğ getiğ skrifağ ykkar eigiğ fall sem keyrir hrağar.

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.
Şiğ şurfiğ ağ búa şessi gögn til sjálf. Til ağ koma ykkur á rétta leiğ er gefiğ fall sem bır til fyrstu gerğina af inntaki. Stærğ inntaksins getur şurft ağ vera nokkuğ mikil. Ekki er ólíklegt ağ şiğ şurfiğ ağ rağa 10 milljón staka fylkjum (eğa stærri) til ağ fá marktækan tíma.

Ş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.


Skiliğ skırslu um framkvæmd tímamælinganna og niğurstöğur úr şeim, ásamt útprentun af forritinu til dæmatímakennara ykkar fyrir kl 18:00 föstudaginn 8. apríl. Şeir munu ekki taka viğ verkefnum sem koma seinna.
annaing (hja) hi.is / hh (hja) hi.is, 21. mars, 2005.