Tehtävä 1 - Ternäärihaku¶

BINSEARCH-proseduuri etsii järjestetystä taulukosta A[1..n] numeroa key käyttäen binäärihakua. Binäärihaussa aloitustaulukko A[L..R] jaetaan kahdeksi lähes yhtä suureksi alitaulukoksi jokaisella iteraatiolla (tai rekursion tasolla): A[L..mid] ja A[(mid+1)..R]. Vertaamalla jakopisteen elementtiä voidaan päätellä, tulisiko etsintää jatkaa vasemmalla vai oikealla puoliskolla (ellei jakopisteessä ole etsittävää elementtiä).

Ternäärihaussa (ternary search) käytetään samankaltaista lähestymistapaa, paitsi että jokaisella iteraatiolla (tai rekursion tasolla) aloitustaulukko A[L..R] jaetaan kolmeksi lähes yhtä suureksi alitaulukoksi: A[L..mid1], A[(mid1+1)..mid2] ja A[(mid2+1)..R]. Numero key voi esiintyä vain yhdessä näistä kolmesta alitaulukosta, ja siksi muut kaksi voidaan jättää huomioimatta.

Kirjoita TERNSEARCH-proseduuri käyttäen ternaarihakua, jonka saat muuttamalla BINSEARCH-pseudokoodia olennaisilta kohdilta.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

BINSEARCH(A,L,R,key)
  input A[1..n] is an array containing numbers; L and R are the
  leftmost and rightmost indices that concern us; key is the value
  we want to find
  output: the index at which key occurs in A, or -1 if it doesn't
  /* The numbers in A must be in order from smallest to largest.
  We search in array A[L..R] for key. If key is found, we return
  its location, otherwise we return -1.*/
  if L == R then
    if A[L] == key then
      return L
    else
      return -1
    end
  else
    mid = floor( (L+R)/2 )
    if key <= A[mid] then
      return BINSEARCH(A,L,mid,key)
    else
      return BINSEARCH(A,mid+1,R,key)
    end
  end

Tehtävä 2 - Luonnollinen mergesort¶

Tässä ongelmassa esimerkkitaulukkona on käytössä A[12, 14, 5, 3, 7, 20, 16, 9] , indeksi i on välillä 1-8. Tavoite on kirjoittaa pseudokoodi luonnolliselle mergesortille, joka järjestää A:n alkiot pienimmästä suurimpaan. Jotta luonnollisen mergesortin toiminnan voisi ymmärtää, tulee ensin ymmärtää käsitteet vähenevä inversio ja sarja (tässä kontekstissa). Järjestettävässä taulukossa on laskeva inversio paikassa i, kun A[i] > A[i+1]. Sarja on taas jokin alitaulukko, jonka alkiot ovat kasvavassa järjestyksessä. Sarjan lopussa on aina vähenevä inversio.

Esimerkkitaulukko voidaan jakaa sarjoihin seuraavasti:

sarja    alkiot
1   [12,14]
2   [5]
3   [3, 7, 20]
4   [16]
5   [9]

Luonnollisessa mergesortissa ensin lomitetaan sarjat 1 ja 2 yhteen, sitten sarjat 3 ja 4, sitten sarjat 5 ja 6, kunnes viimeinen sarja on saavutettu. Tämän jälkeen sarjojsa pitäisi olla jäljellä n. puolet alkuperäisestä määrästä. Sarjoja lomitetaan yhteen, kunnes niitä on vain yksi jäljellä.

Kuvaus luonnollisen mergesortin toiminnasta on annettu myös algoritmissa NATMERGESORT:

NATMERGESORT(*A*)
1. Aloita etsimään laskevien inversioiden sijainteja kohdasta *A[1]*
lähtien. Näiden sijaintien perusteella etsitään alku- ja loppukohdat sarjoille.
2. Lomita peräkkäiset sarjat, kunnes lomitettavia sarjoja ei ole lisää.
3. Toista kohtaa 2, kunnes vain yksi sarja on jäljellä.

Jos NATMERGESORT suoritettaisiin esimerkkitaulukolle, se näyttäisi vaihe vaiheelta tältä:

Taso  askel  muodostetut sarjat
  1   1   [12,14], [5], [3, 7, 20], [16], [9]
  2   2   [5, 12,14], [3, 7, 16, 20], [9]
  3   2   [3, 5, 7, 12,14, 16, 20], [9]
  4   2   [3, 5, 7, 9, 12, 14, 16, 20]

Kirjoita pseudokoodi algoritmille NATMERGESORT.