Sortieren nach Priorität

[iTutHD]

Hallo,
Ich habe folgendes Problem.
Ich muss ein float[]N mit irgend welchen Zahlen und ein float[]p mit Prioritäten sortieren.
Dies soll eine mittlere Laufzeit von n*log(n) haben.

Somit kommt entweder QuickSort oder Mergesort in frage.(sind die einzigen Algorithmen die ich kenne, mir gewünschter Laufzeit)

Jetzt will ich das Array p Sortieren und N als "verknüpft" betrachten. So soll, wenn die Position in p sich ändert, sich auch das Element aus N ändern.

Ich habe doch leider meine Probleme, das zu implementieren. Kann mir wer helfen, bzw. sagen wie ich da gut ansetzten kann?

 

[JCODA]

Jedesmal wenn du die Prioritäten vertauschst, oder ihre Position änderst, änderst du zudem nicht nur die prios sondern auch das Zahlenarray.

 

[iTutHD]

Ich habe mich bei der Aufgabenstellung leider etwas vertan. N ist ein Array vom Datentyp Int und nicht float.
p ist aber trotzdem float. Außerdem soll meine Methode nur N nach der Priorität p returnen.
Ich habe jetzt Mergesort mal folgendermaßen implementiert:

    public static float[] mergeSort(float[] p){
        if(p.length == 1){
            return p;
        }
        else{
            float[] a = mergeSort(Arrays.copyOfRange(p, 0, p.length/2));
            float[] b = mergeSort(Arrays.copyOfRange(p, p.length/2, p.length));
            return merge(a,b);
        }
    }
   
    public static float[] merge(float[] a, float[] b) {
        float[] c = new float[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
        {
            if (a[i] < b[j]) c[k++] = a[i++];
            else c[k++] = b[j++];              
        }
        while (i < a.length) c[k++] = a[i++];
        while (j < b.length) c[k++] = b[j++];
        return c;
    }

Ich hoffe, dass das ganze soweit stimmt. Mein problem ist, dass ich nicht richtig weiß, wie ich N "mitnehmen" soll. Ich muss es ja auf jedenfall schonmal an mergeSort übergeben und mein return auf N ändern. Eigentlich kann ich doch bei der zuweisung für a/b auch noch die gleichen Array Teile an mergeSort übergeben. Jedoch ist da ja noch nicht wirklich etwas passiert. Ich muss es ja schaffen an merge auch mein Array N übergeben. Das ist ja erstmal als parameter kein Problem. Mein Problem ist, dass ich mir nicht sicher bin wie ich merge verändern muss. Eigentlich muss ich doch zusätzlich zu c ein anderes Hilfsarray erstellen und immer wenn c eine zuwesiung bekommt, die selbe für das weiter Hilfsarray, weches N darsellt, machen oder nicht? Leider hat das in meinem Versuch nicht so wirklich geklappt... Ist da nen Denkfehler drin?

 

[thecain]

Das ist ja eine Priority Queue, diese würde ich mit etwas Tree ähnlichem abbilden (AVL, Red Black, you choose)