Array Indizes sortieren

[Wishmaster51]

Hallo,
Ich habe das Anliegen, dass ich zu einem gegebenen double[] Array eine (absteigend) sortierte Liste int[] der Indizes benötige. In der Java-API habe ich dazu nichts gefunden, und auch im Internet gibt es zwar einige Ansätze, aber optimal wäre für mich eine fertige Bibliothek.

Feature Request: Get sorted list of indices of an array | Java.net
Java Array sort: Quick way to get a sorted list of indices of an array - Stack Overflow
java - Get the indices of an array after sorting? - Stack Overflow

 

[Marcinek]

Also du kannst deine doublewerte mit deren aktuellen index in einem Objekt kapseln. dann sorierst du diese anhand der doublewerte.

Oder du sortierst deine doublewerte und bildest jede sortierung auf ein array 1...n ab. Dann hast du die sortierten index.

 

[Wishmaster51]

AHm, notfalls könnte ich es auch selbst schreiben, ich wollte nur mal nachschauen, ob es für so etwas schon eine fertig geschriebene Methode irgendwo gibt.

 

[Timothy Truckle]

Hallo,
Ich habe das Anliegen, dass ich zu einem gegebenen double[] Array eine (absteigend) sortierte Liste int[] der Indizes benötige.

Vielleicht verstehe ich ja Deine Anforderung einfach nicht, aber ein Index in einem Array ist die Position eines Eintrags in diesem Array. Du willst also ein zusätzliches Array anlegen, in dem die einzelnen Positionen extra abgelegt sind? Mal abgesehen davon, dass das mit Array anlegen und for Schleife 'n 3-Zeiler ist, wozu braucht man dass?

bye
TT

 

[DrZoidberg]

Hallo,
Ich habe das Anliegen, dass ich zu einem gegebenen double[] Array eine (absteigend) sortierte Liste int[] der Indizes benötige. In der Java-API habe ich dazu nichts gefunden, und auch im Internet gibt es zwar einige Ansätze, aber optimal wäre für mich eine fertige Bibliothek.

Da ich gerne Werbung für Scala mache, erwähne ich einfach mal, dass dieses Problem in Scala ein Einzeiler ist.

list.zipWithIndex.sortBy(- _._1).map(_._2)

 

[fdhalkwdoph]

Da ich gerne Werbung für Scala mache, erwähne ich einfach mal, dass dieses Problem in Scala ein Einzeiler ist.

list.zipWithIndex.sortBy(- _._1).map(_._2)

Naja, für alle die Scala nicht kennen ist das eher ein "dafuq? 😵" und keine Werbung. Wenn du schon mit solchen Einzeilern Werbung machen möchtest, solltest du es auch erläutern. 🙂

 

[Wishmaster51]

Vielleicht verstehe ich ja Deine Anforderung einfach nicht, aber ein Index in einem Array ist die Position eines Eintrags in diesem Array. Du willst also ein zusätzliches Array anlegen, in dem die einzelnen Positionen extra abgelegt sind? Mal abgesehen davon, dass das mit Array anlegen und for Schleife 'n 3-Zeiler ist, wozu braucht man dass?

Also, ich brauche eigendlich nur die Reihenfolge der Indizes, so dass die zugehörigen Einträge absteigend sortiert sind.

Die Anwendung dahinter ist jetzt etwas aufwendig zu erklären, aber ich habe da noch ein zweites Array der selben Länge, das ich in der Reihenfolge ablaufen will, in der das erste Array sortiert ist. Warum ich das machen will würde nun wirklich zu weit führen...

Ich würde eben ungern nochmal schreiben wenn jemand bereits eine getestete Klasse dafür hat. 😉

 

[Timothy Truckle]

Also, ich brauche eigendlich nur die Reihenfolge der Indizes, so dass die zugehörigen Einträge absteigend sortiert sind.

Nochmal deutlich zum Mitschreiben:
Die Indizes in einem Array sind per Definiton aufsteigend und lückenlos aufeinanderfolgend, und sie existieren nicht physisch in der Struktur

Array

.

Die Liste der Indizes in einem (Java-)Array ist also immer die Folge der natürlichen Zahlen beginnend bei 0 (wobei die Gelehrten noch Streiten ob 0 eine natürlich Zahl ist) bis einschließlich

Länge des Arrays - 1

.

Ich weiß wirklich nicht was Du da noch sortieren willst bzw. musst, oder wieso Du erwartest, dass diese Reihenfolge sich ändern könnte...

bye
TT

 

[Wishmaster51]

Dass die Indizes selbst lückenlos sind ist mir schon klar.

Beispiel:

double[] arr = {6,4,5};

Wenn ich das nun absteigend sortieren möchte, dann ist das Ergebnisarray {6,5,4} und der Indexvektor, an dem ich interessiert bin, ist dann

sort = {1,3,2}

So dass eben sort[0] (=1) den Index des größten Wertes aus arr liefert, sort[2] (=3) würde mir den Index des zweitgrößten Elementes liefern usw...

 

[DrZoidberg]

So etwa?

double[] array = new double[100];
for(int i = 0; i < array.length; i++) {
    array[i] = Math.random();
}

double[][] numberPlusIndex = new double[array.length][];
for(int i = 0; i < array.length; i++) {
    numberPlusIndex[i] = new double[] {array[i], i};
}
Arrays.sort(numberPlusIndex, new Comparator<double[]>() {
    public int compare(double[] npi1, double[] npi2) {
        if(npi2[0] < npi1[0]) return -1;
        else if(npi2[0] > npi1[0]) return 1;
        else return 0;
    }
});
for(double[] npi: numberPlusIndex) {
    System.out.println("Number = " + npi[0]);
    System.out.println("Index = " + (int)npi[1]);
    System.out.println();
}

 

[Timothy Truckle]

Dass die Indizes selbst lückenlos sind ist mir schon klar.

Beispiel:

double arr = {6,4,5};

Wenn ich das nun absteigend sortieren möchte, dann ist das Ergebnisarray {6,5,4} und der Indexvektor, an dem ich interessiert bin, ist dann

sort = {1,3,2}

So dass eben sort[0] (=1) den Index des größten Wertes aus arr liefert, sort[2] (=3) würde mir den Index des zweitgrößten Elementes liefern usw...

Da kommen wir doch der Sache schon näher.

Was Du willst ist also eigentlich den Double- Werten eine ID zuweisen, die die Eingangsreihenfolge widerspiegelt und später diese ID wieder ermitteln zu können.

Das schreit nach einem DTO:

class DoubleWithId implements Comparable<DoubleWithId >{
  private static final Random TEST_DATA = new Random(new Date().getTime());
  private final int id;
  private final double wert;
  public DoubleWithId (int id, double wert){
    this.id = id;
    this.wert = wert; 
  }
 
  public int compareTo(DoubleWithId  o){
    return Double.valueOf(wert).compareTo(Double.valueOf(o.wert));
  }
  public int getId() { return id; }  
  public double getWert() { return wert; }

  public static void main(String[] args){
    List <DoubleWithId> myList = new ArrayList<>();
    while (100<myList.size()){
       myList.Add(new DoubleWithId (myList.size(), TEST_DATA.nextDouble()*100));
    }
   Collections.sort(myList);
   Collections.reverse(myList);
   for(DoubleWithId  doubleWithId  : myList){
     System.out.println("Wert "+doubleWithId.getWert() + " hat ID "+ doubleWithId.getId());
   }

  };

bye
TT

 

[Wishmaster51]

Da kommen wir doch der Sache schon näher.

Was Du willst ist also eigentlich den Double- Werten eine ID zuweisen, die die Eingangsreihenfolge widerspiegelt und später diese ID wieder ermitteln zu können.

Ja, genau, ich habe hier ein Rucksackproblem, von denen der Array, den ich sortieren will, die Werteffizienz der Objekte (Nutzen pro Gewichtseinheit) angibt, und der andere Array gibt mir das Gewicht an.

Nun will ich im ersten Schritt einen Greedy-Algorithmus umsetzen, d.h. ich verwende zuerst das Objekt mit der größten Werteffizienz, dann das zweitgrößte....Dazu brauch ich eben die Umindizierung.

Danke für eure Codestücke, werde mir das mal ansehen 🙂

 

[Timothy Truckle]

Ja, genau, ich habe hier ein Rucksackproblem, von denen der Array, den ich sortieren will, die Werteffizienz der Objekte (Nutzen pro Gewichtseinheit) angibt, und der andere Array gibt mir das Gewicht an.

Dann könntest Du doch ganz ohne Indexfummelei die Gewichte statt der Indices in den DTOs speichern...

bye
TT

 

[Gast2]

Ja, genau, ich habe hier ein Rucksackproblem, von denen der Array, den ich sortieren will, die Werteffizienz der Objekte (Nutzen pro Gewichtseinheit) angibt, und der andere Array gibt mir das Gewicht an.

Nun will ich im ersten Schritt einen Greedy-Algorithmus umsetzen, d.h. ich verwende zuerst das Objekt mit der größten Werteffizienz, dann das zweitgrößte....Dazu brauch ich eben die Umindizierung.

Poste sowas das nächste mal direkt im ersten Post, dann hätte man sich das ganze gerate in den vorherigen Posts sparen können.

Anstatt mit zwei Arrays rumzuhantieren solltest du Gewicht und Nutzen in einer Klasse kapseln und diese Objekte in eine Liste legen. Mit nem entsprechenden Comparator kannst du das ganze dann z.b. nach Gewicht sortieren.

 

[Landei]

Wenn es keine Duplikate unter den doubles gibt...

    public static int[] indexes(double values[]) {
        TreeMap<Double,Integer> map = new TreeMap<Double, Integer>();
        for(int i = 0; i < values.length; i++) {
            map.put(values[i], i);
        }
        int[] result = new int[map.size()];
        int i = 0;
        for(Integer value : map.values()) {
            result[i++] = value;
        }
        return result;
    }

 

[Timothy Truckle]

[...]

Zu spät, sein Problem war eigentlich ein anderes...

bye
TT

 

[Wishmaster51]

Danke für eure Antworten. Muss mir noch überlegen, wie genau ich es implementiere. 🙂