Tietorakenteet / syksy 2009 / Linna

Harjoitus 2, viikko 38

1. Tarkastellaan seuraavien kokonaislukujonojen lajittelua pikalajittelua käyttäen.

Kuvaile lajittelun kulkua.

a) 7,6,10,1,9,12,8,3,11,2,4,5

b) 12,11,10,9,8,7,6,5,4,3,2,1

2. Olkoon lajiteltavana edellisen tehtävän lukujonot. Kuvaile lajittelun kulkua, kun lajittelumenetelmänä on ShellSort.

3. Mikä on pikalajittelun aikakompleksisuus, jos lajiteltavat alkiot ovat

a) valmiiksi järjestyksessä,

b) käänteisessä järjestyksessä ?

4. Olkoon annettu lista L ja toinen lista P, joka sisältää positiivisia kokonaislukuja

suuruusjärjestyksessä. Operaatio printLots(L,P) tulostaa listan L ne alkiot,

joiden paikat määräytyvät listan P alkioiden mukaan. Jos siis esimerkiksi P = 1,

3, 4, 6, niin listan L paikoissa 1, 3, 4 ja 6 olevat alkiot tulostuvat. Laadi ohjelma

printLots(L,P).

5. Laadi algoritmi Same(A,B), joka palauttaa arvon true, jos lineaarisen listan

A sisältö on sama kuin lineaarisen listan B sisältö.

6. Tarkastellaan seuraavaa peliä (Josephus problem): N henkilöä, numeroituna 1:stä N:ään istuvat pyöreän pöydän ympärillä. Alkaen henkilöstä 1 ojennetaan aina vieressä istuvalle kuuma peruna. Aina M:n askeleen jälkeen henkilö, jolla peruna on, putoaa pois pelistä ja peli jatkuu samalla periaatteella pudonneesta henkilöstä seuraavana olevasta. Viimeisenä pöytään jäävä on voittaja. Jos esimerkiksi M = 0 ja N = 5, niin pelaajat eliminoituvat järjestyksessä. Jos taas esimerkiksi M = 1 ja N = 5, niin eliminointijärjestys on 2, 4, 1, 5 ja siis henkilö numero 3 voittaa. Laadi ohjelma joka ratkaisee probleeman yleisillä arvoilla M ja N. Mikä on ohjelmasi vaatiman ajan suuruusluokka?