Programatori a programatorky! Blackhole.sk v spolupraci s mojou malickostou vyhlasuje prve (a snad nie posledne (uvidime aky bude ohlas ;)) ) kolo Blackhole programming contestu.Vasou prvou ulohou bude naprogramovat najmensiu implementaciu insert sortu.Myslim ze kazdemu je jasne ze je to jedine mozne robit v asm. Takze chytte svoje zbrane (kompilatory a debugery) a siahnite az za hranice svojich ludskych schopnosti! :).
Problem:
- urobit najmensiu implementaciu insert sortu.
Podmienky:
- musi fungovat pre akekolvek 32 bitove cislo
- musi fungovat pre akekolvek hodnoty
- funkcia sa nesmie spoliehat na hodnoty v registroch ktore boli do nich ulozene pred jej zavolanim
Popis insert sortu:
Algoritmus zacina od druheho prvku pola.Tato hodnota sa nasledne porovnava s hodnotami na nizsich indexoch pola a konci sa vtedy ak:
1) nasa hodnota 'x' je vacsia ako hodnota na danom indexe pola
2) pokial sme narazili na lavy koniec pola
Pri kazdom porovnani sa nasledne musi urobit presun hodnoty z nizsieho indexu na vysii.Cize akysi pseudokod:
while index < sizeof(pole)
temp = pole[index]
r = index - 1;
for pokial je r nula alebo temp je mensie ako pole[r]
urob presun pole[r] do pole[r + 1]
presun temp do pole[r + 1]
Teda prakticky priklad:
3 1 2
1) zaciname od druheho prvku pola,tento ma hodnotu 1
2) postupujeme smerom dolava kde nachadzame 3
3) kedze 3 > 1 urobime vymenu
4) a kedze sme na konci pola,zvysime nas index o 1 a ideme od zaciatku
1 3 2
5) hodnota na pole[index] je 2 a 3 > 2 takze nastane vymena
6) hodnota na prvom prvku je 1 a 1 < 2 tak cyklus ukoncime
7) index dosiahol koniec pola,preto sa algoritmus konci
1 2 3
Prevedenie:
- aby som mohol objektivne rozhodnut o tom kto vyhraje resp aby ste sa plne mohli sustredit na riesenie problemu,tak vsetci budete pisat od isteho zakladu ktory sa nachadza tu ISORT.C z tohto zdrojaku sa vola funkcia sort().za touto funkciou si robte co chcete.
-program bude brat hodnoty z prikazoveho riadku
Hodnotenie:
-predstavoval som si to tak ze programu nahadzem hockjake cislaco mi pridu pod ruku,alebo cisla s ktorymi som mal problemy ja.
-pripadne vyuzijem sluzby shellu a jeho premennej $RANDOM :)
-ak mate ine napady alebo vyhrady ci pripomienky tak moj mail viete ;),pripadne na boarde
Moje riesenie: svoje riesenie zverejnim az po skonceni sutaze.
Vyhra: dozivotna slava a ospevovanie na boardoch blackholu ;)A preco to vsetko?: len tak...pre srandu ;
Nuze a ako posledna ta najdolezitejsia otazka...kolko casu? Hmm noo mne to tiez trvalo dlhsie ako som predpokladal ale tiez si myslim ze su tu aj sikovnejsi ludia tak vam dam 3 tyzdne ;
vysledky zasielajte na dole uvedeny mail. diskusia povolena v komentaroch pod clankom :
v92,v92@hysteria.skv92
