Algoritmer og datastrukturer

Programmeringsprosjekt: Sortering med heap

Merk: Dette er ikke en obligatorisk oppgave, men en øvingsoppgave som du ikke skal levere inn.

I denne oppgaven skal du bruke en binær heap til å sortere data. Vi skal begrense oss til å se på sortering av arrayer/tabeller med heltall.

Vi vet at heapen er "lynrask" med hensyn til innsetting og fjerning av data. En heap har alltid O(log n) effektivitet, der n er antallet verdier som er lagret i heapen.

Dette kan vi utnytte til å lage en effektiv sorteringsalgoritme, fordi en min-heap alltid vil "levere tilbake" dataene vi putter inn i den i sortert rekkefølge: Hver gang vi fjerner en verdi fra heapen er det alltid den minste verdien som tas ut.

Følgende algoritme vil sortere en array med data med bruk av en heap:

  1. Sett alle de n elementene i arrayen inn i en heap som initielt er tom.

  2. Ta ut minste element av heap'en n ganger og sett dem tilbake i arrayen i sortert rekkefølge.

Merk at denne algoritmen vil bruke en ekstra array til å lagre heapen. Den vil altså kreve like mye ekstra minne som dataene som skal sorteres. Det finnes smartere måter å gjøre heapsort på som er "in-house", dvs. at sorteringen gjøres "inne i" den opprinnelige arayen uten å kreve ekstra minne.

Oppgave 1

Programmer en metode:

void heapSort(int A);

som sorterer en array med heltall ved å bruke algoritmen med to steg som er gitt ovenfor. For å lagre tallene i A i en heap, skal du bruke implementasjonen av heap med heltall som er gitt i læringsmodulen i Canvas:

   IntHeap.java→

For å bruke denne koden kan du bare laste den ned til samme katalog som du bruker for metoden heapSort().

Oppgave 2

Lag også et testprogram som gjør følgende:

  • Leser antall tall som skal sorteres, n, fra bruker.

  • Oppretter en array av lengde n og fyller denne med tilfeldige tall som er større eller lik 0 og mindre enn 2·n.

  • Sorterer arrayen med metoden du laget i oppgave 1.

  • Tar tiden på sorteringen og skriver ut antall millisekunder som det tok å sortere tallene.

Oppgave 3

Hva er arbeidsmengden, uttrykt med O-notasjon, til metoden du laget i oppgave 1?