Sortiranje s kopico

Lastnosti kopice

• kopica je binarno drevo
• vozlišče drevesa ustreza objektu v tabeli
• za vsako vozlišče velja, da je objekt večji ali enak od vseh naslednikov
• dolžini dveh poljubnih vej v kopici se razlikujeta kvečjemu za ena, daljše veje so skrajno levo

Primer kopice

Na vrhu je največji element.

Ponazoritev kopice v računalniku

• še vedno sortiramo tabelo Element[] a
• koren je v a[0]
• levi sin vozlišča a[i] je v a[2*i+1]
• desni sin vozlišča a[i] je v a[2*i+2]

/----d--.
|-l-.
0   1   2   3   4   5   6   7   8   9
75  31  62  29  18  45  61  21  25  7
    |---l---^
     \-------d--^

Opis algoritma

1. vhodno zaporedje uredimo v kopico
2. zamenjamo prvi in zadnji element v kopici
3. popravimo kopico
4. Ponavljamo koraka 2 in 3, dokler ne zmanjka podatkov

Primer delovanja

6 5 1 2 4 8

Gradnja kopice

Gremo od zadaj naprej in poiščemo 1. element ki ima naslednika. Potem preverimo če je element ustrezno urejen ali ne. Če ni je treba zadevo popraviti in elementa zamenjati med seboj.

Gradnja 1: Zamenjamo 8 in 1, v koren premaknemo večjo vrednost (ali manjšo če bi urejali padajoče)

Gradnja 2: primerja 5 z 2 in 4, ker je že urejen, ne spremeni nič.

Gradnja 3: Zamenjamo 8 in 6. Ker je ostanek drevesa zgrajen, končamo z grajenjem.

Urejanje kopice

Ko je kopica zgrajena lahko začnemo z urejanjem. Sivo so pobarvani elementi ki so že sortirani. Modro pa so pobarvane izvedene zamenjave.

Zamenjava 1: Vedno zamenjamo prvi in zadnji element v kopici

Popravljanje 1: Kopico popravljamo kot pri gradnji, ne popravljajoč že sortirane elemente (8)

Zamenjava 2: Zamenjamo prvi in zadnji element. Ker je 8 že sortirano in ga ne upoštevamo, zadnji element je pred zamenjavo bil 4. Z zamenjavo smo sortirali še 6.

Popravljanje 2: Popravimo kopico ne upoštevajoč 6 in 8

Zamenjava 3: Zamenjamo 5 in 2, ker sta 8 in 6 že sortirana. S tem je sortiran tudi 5.

Popravljanje 3: Popravimo kopico, enako kot smo to počeli pri gradnji, tako da pogrezamo največje člene v koren (začetek).

Zamenjava 4:

Popravljanje 4:

Zamenjava 5:

6 5 1 2 4 8
            d1
6 5 8 2 4 8
            d2
6 5 8 2 4 1
            d3
8 5 6 2 4 1
------------z1
1 5 6 2 4 8
            p1
6 5 1 2 4 8
            z2
4 5 1 2 6 8
            p2
5 4 1 2 6 8
            z3
2 4 1 5 6 8
            p3
4 2 1 5 6 8
            z4
1 2 4 5 6 8
            p4
2 1 4 5 6 8
            z5
1 2 4 5 6 8

Gradnja kopice

• uporabimo postopek pogrezanja
• objekti v desni polovici tabele (i>=a.length/2) nimajo naslednikov
• objekte pogrezamo v zanki od sredine tabele proti začetku

Algoritem v Javi

public static void heapsort(Element[] a)
  {
    Element x;
    for (int l=a.length/2-1; l>=0; --l)
    {
      heapify(a,l,a.length-1);
      System.out.println("po Heapify("+l+","+(a.length-1)+")");     
      a[0].izpisiTabelo(a);      
    }
    for (int r=a.length-1; r>0; --r)
    {
      x=a[0];
      a[0]=a[r];
      a[r]=x;
      System.out.println("po zamenjavi(0,"+r+")"); 
      a[0].izpisiTabelo(a);      
      heapify(a,0,r-1);
      System.out.println("po Heapify(0,"+(r-1)+")"); 
      a[0].izpisiTabelo(a);      
    }
  }

public static void heapify(Element[] a,int l, int r)
  {
    int i=l, j=2*i+1;
    Element x=a[i];
    while (j<=r)  // dokler obstaja naslednik (naslednik je v mejah kopice)
    {
      if ((j<r) && (a[j].manjsi(a[j+1]))) ++j;   // a[j] je vecji naslednik
      if (!(x.manjsi(a[j]))) break;
      a[i]=a[j];
      i=j;
      j=2*i+1;        
    }
    a[i]=x; 
  }

Analiza časovne kompleksnosti

gradnja kopice na začetku

O(log2 n)

popravljanje kopice

O(log2 n)

zamenjava prvega in zadnjega objekta

O(n)

Skupaj

Tw = O(n*log2 n)

G

gradnja

Z

zamenjava

P

popravljanje

M: G, Z+P

G:

G:

Z:

P:

Povezave

• Opis, razlaga + učenje s pomočjo Java appleta
• Java simulacija - primerjava urejenosti in kopice
• Java simulacija s poudarkom na kopici