Mer om arrayer

• Sortering av array
• Søking i arrayer
  • Binær søking

Sortering av array

Av erfaring vet vi at søking kan utføres langt mer effektivt når vi har en datamengde som er sortert, jf. oppslag i ordbok eller leksikon som ikke er elektronisk. Det finnes mange forskjellige algoritmer (framgangsmåter) for sortering. Noen er enkle og lett forståelige. Andre er mer kompliserte å forstå, men desto mer effektive på store datamengder. Sorteringsmetoder blir studert inngående i et seinere kurs (Algoritmer og datastrukturer). Her skal vi nøye oss med å se på en enkel sorteringsmetode, slik at vi kjenner til en metode i tilfelle vi har behov for sortering.

De enkle, rett-fram-metodene har tilfredsstillende effektivitet når datamengdene ikke er for store, det vil si opp til noen hundre elementer, avhengig av hvor store elementene er. (Store dataelementer er det mer tidkrevende å flytte.) Vi skal ta for oss den enkle metoden som på engelsk kalles Selection Sort. På norsk kan vi kanskje kalle den "sortering ved utvelging". Navnet kommer av at vi hele tida velger det minste av de usorterte elementene og bytter dette elementet med det første blant de usorterte. (Det er her forutsatt at vi skal sortere i voksende rekkefølge.) Ved sortering generelt, blir de størrelsene som sammenliknes for å avgjøre rekkefølge kalt for sorteringsnøkler, eller kort og godt nøkler. (I tillegg til tall, kan det for eksempel være String-objekter.)

Et overordnet krav ved all sortering er for øvrig det vi kan kalle økonomisk bruk av tilgjengelig lagerplass. Ved array-sortering betyr dette at nødvendig permutasjon av elementer må finne sted i arrayen selv. Metoder som flytter elementer fra en gitt array over til en resultatarray er av mindre interesse. Dette med økonomisering av lagerplassen var særlig viktig tidligere, da datamaskinene hadde mye mindre kapasitet enn vi er vant med. Likevel brukes det fortsatt mest sorteringsmetoder som foretar all flytting innenfor den array som skal sorteres.

Selection Sort

Sorteringsprinsipp (skal sortere n elementer d0, d1, ..., dn-1):

1. Velg elementet med minst nøkkel.
2. Bytt om dette med det første elementet d0.
3. Gjenta de to første operasjonene med de n - 1 gjenværende elementene, deretter med n - 2 elementer, etc. inntil bare ett element — det største — er igjen.

Det kan være instruktivt å se hvordan prosessen virker på et konkret sett av nøkkelverdier. I tabellen nedenfor er øverste rad de opprinnelige nøklene som skal sorteres. Hver ny rad viser rekkefølgen etter et nytt skritt i sorteringsprosessen. (I programmeringssammenheng vil det bety etter et nytt gjennomløp av en løkke.) Elementet med minst nøkkel i hvert skritt er gjengitt med uthevet skrift. Elementene som er ferdig sortert er gjengitt med skråskrift.

	44      55      12      42      94      18       6      67
	6       55      12      42      94      18      44      67
	6       12      55      42      94      18      44      67
	6       12      18      42      94      55      44      67
	6       12      18      42      94      55      44      67
	6       12      18      42      44      55      94      67
	6       12      18      42      44      55      94      67
	6       12      18      42      44      55      67      94

Dersom arrayen som inneholder elementene heter d og det er n elementer som skal sorteres (fra starten av arrayen, i voksende rekkefølge), kan vi i pseudokode formulere algoritmen slik:

  for ( int i = 0; i < n - 1; i++ )
  {
    < finn indeks min til den minste verdi blant d[i], ..., d[n-1] >
    < bytt om d[i] og d[min] >
  }

Algoritmen er implementert i static-metoden sorter i klassen Arraymetoder som er gjengitt nedenfor. Sorteringsmetoden mottar som parameter den arrayen som skal sorteres. Klassen inneholder også en static-metode som skriver ut en array i et tekstområde. Array og tekstområde mottas som parametre. Programmet Sorteringstest.java som er gjengitt etter klassen Arraymetoder, tester sorteringsmetoden på de samme data som er vist ovenfor. Resultatet kan du se i følgende bilde av programmets utskrift.

 1 import javax.swing.JTextArea;
 2
 3 public class Arraymetoder
 4 {
 5   //sorterer tabellen data ved bruk av algoritmen Selection Sort
 6   public static void sorter(int[] data)
 7   {
 8     for (int i = 0; i < data.length - 1; i++)
 9     {
10       int min = i;
11       //finner det minste element blant de usorterte
12       for (int j = i + 1; j < data.length; j++)
13       {
14         if (data[ j] < data[ min])
15         {
16           min = j;
17         }
18       }
19
20       //bytter om elementer
21       int temp = data[ min];
22       data[ min] = data[ i];
23       data[ i] = temp;
24     }
25   }
26
27   //skriver ut array i tekstområde med 10 tall per linje
28   public static void skrivTabell(JTextArea utskrift, int[] tabell)
29   {
30     for (int i = 0; i < tabell.length; i++)
31     {
32       utskrift.append(tabell[ i] + "  ");
33       if ((i + 1) % 10 == 0)
34       {
35         utskrift.append("\n");
36       }
37     }
38   }
39 }

 1 //Sorterer en tabell ved bruk av metoden Selection Sort.
 2 //Skriver ut tabellinnhold før og etter sortering.
 3 import javax.swing.JTextArea;
 4 import javax.swing.JOptionPane;
 5
 6 public class Sorteringstest
 7 {
 8   public static void main( String[] args )
 9   {
10     JTextArea utskrift = new JTextArea();
11     utskrift.setEditable( false );
12     int[] tabell = { 44, 55, 12, 42, 94, 18, 6, 67 };
13     utskrift.setText( "Tabell for sortering:\n" );
14     Arraymetoder.skrivTabell( utskrift, tabell );
15
16     //sorterer tabellen:
17     Arraymetoder.sorter( tabell );
18     //skriver ut sortert tabell:
19     utskrift.append( "\n\nSortert tabell:\n" );
20     Arraymetoder.skrivTabell( utskrift, tabell );
21     JOptionPane.showMessageDialog( null, utskrift, "Sorteringstest",
22         JOptionPane.PLAIN_MESSAGE );
23   }
24 }

Søking i array

Enkleste søkemetode i en array er sekvensiell søking: For å finne elementet som vi leter etter, besøker vi elementene etter tur i den rekkefølge de står i arrayen. I snitt må da halve arrayen gjennomsøkes før det søkte element blir funnet, eller eventuelt det kan fastslås at det ikke finnes. Sekvensiell søking er den mest ineffektive søkemetoden. Men dersom arrayen ikke er sortert, eller elementene ikke er plassert på en annen systematisk måte, er det ingen bedre måte å utføre søkingen på.

Dersom det søkte elementet ikke finnes, må søkemetoden returnere et passende signal for det, for eksempel verdien -1, siden -1 ikke kan være arrayindeks. En søkemetode for sekvensiell søking i en array av heltallsverdier kan derfor skrives slik:

  int search( int[] kilde, int nøkkel )
  {
    for ( int i = 0; i < kilde.length; i++ )
      if ( kilde[ i ] == nøkkel )
        return i;
    return -1;
  }

Legg merke til at dersom den søkte verdien blir funnet, vil metoden returnere arrayindeksen for denne umiddelbart og avslutte søket. Verdien -1 vil bare bli returnert i det tilfelle at metoden kommer gjennom hele for-løkka uten å ha funnet den søkte verdien.

I sorterte arrayer finnes det søkemetoder som er langt mer effektive enn sekvensiell søking og som derfor bør foretrekkes. En slik metode er binær søking, som vi nå skal se på. Som i tilfelle sortering, kaller vi nøkkelverdier, eller kort nøkler, de verdiene vi søker etter.

Binær søking

Forutsetning: sortert array.
Søkestrategi: Se først midt i arrayen. I tilfelle ikke funn: avgjør ved sammenlikning av nøkkelverdier om søkingen skal fortsette i venstre eller høyre del av arrayen. Benytt samme strategi om igjen på denne.

Søkestrategien er implementert i static-metoden binærsøk som er gjengitt nedenfor. Metoden er tilføyd til klassen Arraymetoder som vi brukte i programeksemplet Sorteringstest foran.

40   //Foretar binærsøking etter nøkkel i arrayen tabell.
41   //Returner indeksposisjon, eller -1 i tilfelle ikke funn.
42   public static int binærsøk( int[] tabell, int nøkkel )
43   {
44     int venstre = 0, høyre = tabell.length - 1, midt;
45     while ( venstre <= høyre )
46     {
47       midt = (venstre + høyre) / 2;  //skal lete midt i tabellen
48       if ( tabell[ midt ] < nøkkel )
49         venstre = midt + 1; //dropper venstre halvdel av tabellen
50       else if ( tabell[ midt ] > nøkkel )
51         høyre = midt - 1; //dropper høyre halvdel av tabellen
52       else
53         return midt; //fant den. Returnerer indeks for funnsted og går ut
54     }
55     return -1;  //nøkkel fantes ikke. Signaliserer dette ved retur av -1.
56   }
57 }
58

Vi skal teste metoden for binærsøking i programmet BinarySearch.java som er gjengitt nedenfor. (NB! Programmet er et hendelsesbasert vindusprogram og forutsetter at du har gjort deg kjent med stoffet i kapitlet Vindusbaserte programmer.) Programmet oppretter en array som inneholder alle partall fra og med 0 til og med 1000. Brukeren kan søke etter tall ved å skrive tallet inn i et tekstfelt og trykke Retur-tast. Programmet svarer med å skrive ut indeksposisjon for tallet i tilfelle det finnes i arrayen, eller melding om at tallet ikke finnes. Bildet nedenfor viser programvinduet etter at det er søkt på tallet 998. Driverklasse med main-metode for programmet finnes i fila Searchtest.java

 1 import java.awt.*;
 2 import java.awt.event.*;
 3 import javax.swing.*;
 4
 5 public class BinarySearch extends JFrame implements ActionListener
 6 {
 7   private JTextField input;
 8   private JLabel output;
 9   private int[] testliste;
10   public static final int ANTALL = 501; //arraystørrelse
11
12   public BinarySearch()
13   {
14     super("Test på binærsøking");
15     Container c = getContentPane();
16     c.setLayout(new FlowLayout());
17     c.add(new JLabel(
18             "Søker i sortert array med alle partall fra 0 til 1000."));
19     c.add(new JLabel("Dvs. partallet k befinner seg i posisjon k/2."));
20     c.add(new JLabel("Velg tall det skal søkes etter: "));
21     input = new JTextField(10);
22     c.add(input);
23     output = new JLabel();
24     c.add(output);
25     genererListe();
26     input.addActionListener(this);
27   }
28
29   private void genererListe()
30   {
31     testliste = new int[ANTALL];
32     for (int i = 0; i < testliste.length; i++)
33     {
34       testliste[ i] = 2 * i;
35     }
36   }
37
38   public void actionPerformed(ActionEvent e)
39   {
40     int nøkkel = Integer.parseInt(input.getText());
41     int pos = Arraymetoder.binærsøk(testliste, nøkkel);
42     if (pos >= 0)
43     {
44       output.setText(nøkkel + " finnes i posisjon " + pos);
45     }
46     else
47     {
48       output.setText(nøkkel + " finnes ikke.");
49     }
50   }
51 }

Litt om effektiviteten til binær søking

Ved binær søking halverer vi for hvert nytt skritt det antall elementer som det søkes blant. Dersom vi i utgangspunktet skal søke blant n elementer, vil derfor det maksimale antall halveringer vi kan foreta før vi står igjen med en tom liste av elementer, være det minste tallet k vi kan bruke slik at 2k er lik eller større enn n. For eksempel har vi at 2⁴ er lik 16. For 16 elementer trenger vi derfor maksimalt 4 "oppslag". Videre er 2¹⁰ lik 1024. Når vi bruker binær søking på inntil 1024 elementer, trenger vi derfor maksimalt 10 "oppslag" for å finne elementet, eller fastslå at det ikke finnes. 2²⁰ er lik 1048576. Det betyr at vi maksimalt trenger 20 "oppslag" ved binær søking på en million elementer. Det må vi vel kunne si er svært effektiv søking!

Oppgave 1

a) Metoden

  public static void sorter( int[] data )

som er beskrevet ovenfor, sorterer arrayen data i voksende rekkefølge. For at metoden skal virke riktig, må imidlertid arrayen være full - det kan ikke være noen ledige plasser. Du får som oppgave å modifisere metoden, slik at den også virker riktig når det er ledige plasser i arrayen. Metoden må da få vite hvor mange tall som er lagt inn i arrayen. Det kan den få vite via en ekstra parameter. Du skal altså skrive en metode

  public static void sorter( int[] data, int antall )

der antall er antall tall som er lagt inn i arrayen data. (Vi forutsetter at eventuelle ledige plasser er på slutten av arrayen.) Metoden skal sortere tallene i voksende rekkefølge.

Oppgave 2

Metoden

  public static int binærsøk( int[] tabell, int nøkkel )

som er beskrevet ovenfor, foretar binærsøking etter tallet nøkkel i arrayen tabell. (Arrayen må på forhånd være sortert.) Metoden virker imidlertid riktig bare i det tilfelle at arrayen er full. Du får som oppgave å modifisere metoden, slik at den også virker riktig når det er ledige plasser på slutten av arrayen. Du skal altså skrive en metode

  public static int binærsøk( int[] tabell, int nøkkel, int antall )

som foretar binærsøking i arrayen tabell etter tallet nøkkel. Antall tall i arrayen er lik verdien til parameteren antall. Metoden skal returnere array-indeksen til nøkkel dersom tallet finnes i arrayen, -1 dersom tallet ikke finnes.

Oppgave 3

Du skal nå gjøre bruk av metodene sorter og binærsøk som du skrev i oppgave 1 og 2. Det skal du gjøre ved at du modifiserer programmet du skrev til oppgave 4 i kapittel 7. Programmet gikk ut på å lese inn 20 forskjellige tall fra brukeren og lagre dem i en array. Tallene skulle være fra intervallet 20 til 100. For hvert innlest tall skulle det sjekkes om tallet allerede fantes i arrayen. Dersom det ikke fantes, skulle det legges inn på første ledige plass.

Du skal modifisere programmet ved at arrayen som inneholder de innleste tallene hele tida holdes sortert i voksende rekkefølge. Det oppnår du ved at du for hvert nytt tall som er lagt inn i arrayen gjør kall på metoden sorter, brukt på arrayen.

Du skal også modifisere programmet ved at metoden finnes skal bruke binærsøking for å sjekke om det innleste tallet allerede finnes i arrayen. (Inne i finnes gjør du kall på metoden binærsøk for å sjekke om tallet finnes i arrayen. Returverdien fra binærsøk bruker du for å finne ut om returverdien fra finnes skal være true eller false.) Dersom du programmerer riktig, vil du se at når programmet skriver ut tallene som er lagret i arrayen, så vil de alltid komme i voksende rekkefølge.

Copyright © Kjetil Grønning og Eva Hadler Vihovde, revidert 2014