[Løst] metode for å returnere en int-tabell med sortert indeks

[Not Impressed]

Skal lage en metode hvor metoden skal motta en tabell på minimum 3 verdier. Utifra den tabellen skal det plukkes ut de tre første verdiene. Indeksen til de tre første verdiene skal returneres i en int tabell.

Eks: int[] a = {9,5,7} så skal det returneres {1,2,0}. Dette fordi a[1] = 5, a[2] = 7 og a[0] = 9.

I {1,3,2} skal det returneres {0,2,1}. Tabell a skal ikke endres.

public class Testprogram {

    public static void main(String[] args) {
        int[] a = {9,8,7,2,7,8};
        System.out.println(Arrays.toString(indeks(a)));
        
    }
    
   public static int[] indeks(int[] a)
   {
        int n = a.length;
       
        if (n < 3)
        {
            throw new IllegalArgumentException("tabellen må ha minst 3 elementer!"); 
        }
        
        
        int min = 0;                    //minste indeks
        int nmin = 1;                   //nest minste indeks
        int tmin = 2;                   //tredje minste indeks
        
        // Kontrollerer at de tre verdiene vi starter med er i riktige posisjoner
        if (a[2] < a[1] && a[1] < a[0]) 
        { 
            min = 2; 
            nmin = 1; 
            tmin = 0; 
        } 
        else if (a[2] < a[0] && a[0] < a[1]) 
        { 
            min = 2; 
            nmin = 0; 
            tmin = 1; 
        } 
        else if (a[1] < a[2] && a[2] < a[0]) 
        { 
            min = 1; 
            nmin = 2; 
            tmin = 0; 
        } else if (a[1] < a[0] && a[0] < a[2]) 
        { 
            min = 1; 
            nmin = 0; 
            tmin = 2; 
        } 
        else if(a[0] < a[1] && a[1] < a[2]) 
        { 
            min = 0; 
            nmin = 1; 
            tmin = 2; 
        } else if(a[0] < a[2] && a[2] < a[1]) 
        { 
            min = 0; 
            nmin = 2; 
            tmin = 1; 
        }

        int[] indeks = new int[] {min, nmin, tmin};

        return indeks;
    }
} 

Jeg mener at jeg har fått til en (om noe (garantert) for mye kode) metode som gjør jobben. Men dette skal være mulig med kun tre sammenligninger og maks tre ombyttinger. Her har jeg 7 sammenligninger om man tar med if (n < 3).

Noen tanker eller idéer på hvordan dette kan forbedres?

[jonny]

Du kan gjøre det slik:
1. Opprett resultattabellen slik: "int[] indeks = {0, 1, 2};"
2. Sjekk om a[indeks[1]] < a[indeks[0]], bytt elementene 0 og 1 i indeks hvis dette er sant
3. Sjekk om a[indeks[2]] < a[indeks[1]], bytt elementene 1 og 2 i indeks hvis dette er sant
4 Gjenta step 2
5. returner indeks

Her er noe av det samme, men her returneres en array med samme lengde som input-arrayen (dette kalles forresten innsettingssortering):

import java.util.Arrays;

public class Testprogram {

  public static void main(String[] args) {
    int[] a = {9,8,7,2,7,8};
    System.out.println(Arrays.toString(sortedIndexes(a)));
  }
    
  public static int[] sortedIndexes(int[] a) {
    int[] result = new int[a.length];

    for (int i = 1, j = i; i < a.length; i++, j = i) {
      while (j > 0 && a[i] < a[result[j-1]])
        result[j] = result[--j];
      result[j] = i;
    }

    return result;
  }

} 

Faktisk trenger du ikke gjøre noen ombyttinger i det hele tatt (noe du jo heller ikke gjør i koden din). Det holder med 2-3 sammenligninger, slik som koden under viser:

  public static int[] sortedIndexes3(int[] a) {
    if (a.length < 3)
      throw new IllegalArgumentException();

    return (a[1] < a[0] ?
             (a[2] < a[1] ? new int[] {2, 1, 0}
             : (a[2] < a[0] ? new int[] {1, 2, 0} : new int[] {1, 0, 2}))
           : (a[2] < a[0] ? new int[] {2, 0, 1}
             : (a[2] < a[1] ? new int[] {0, 2, 1} : new int[] {0, 1, 2})));
  }

Endret 14. september 2015 av jonny

[Not Impressed]

 

Du kan gjøre det slik:

1. Opprett resultattabellen slik: "int[] indeks = {0, 1, 2};"

2. Sjekk om a[indeks[1]] < a[indeks[0]], bytt elementene 0 og 1 i indeks hvis dette er sant

3. Sjekk om a[indeks[2]] < a[indeks[1]], bytt elementene 1 og 2 i indeks hvis dette er sant

4 Gjenta step 2

5. returner indeks

 

Her er noe av det samme, men her returneres en array med samme lengde som input-arrayen (dette kalles forresten innsettingssortering):

import java.util.Arrays;

public class Testprogram {

  public static void main(String[] args) {
    int[] a = {9,8,7,2,7,8};
    System.out.println(Arrays.toString(sortedIndexes(a)));
  }
    
  public static int[] sortedIndexes(int[] a) {
    int[] result = new int[a.length];

    for (int i = 1, j = i; i < a.length; i++, j = i) {
      for (; j > 0 && a[i] < a[result[j-1]]
        result[j] = result[--j];
      result[j] = i;
    }

    return result;
  }

} 

Takker så mye!