Sequenzen sortieren

[techdevil]

Hi,

gegeben sind 2 Arrays A=18,4,2,7 und B=4,1,3,2
A ist das zu sortierende Array. B ist das "Muster" nachdem sortiert werden soll.
Gesucht ist ein Sortieralgorithmus, sodass am Ende A=4,7,2,18 ist.
Er soll zudem im Schnitt O(nlogn) benötigen.
Jemand nen Tip?

 

[javimka]

Zuerst normal sortieren und dann gemäss B permutieren.

 

[techdevil]

Zuerst normal sortieren?
Also so, dass A=2,4,7,18 ?

 

[javimka]

ja genau

 

[techdevil]

Und B bleibt so wie es ist?
Ich befürchte ich weiss nicht so recht wie man "permutiert"..

 

[javimka]

Also wenn du A sortiert hast, kannst du einfach die Einträge gemäss B vertauschen (=permutieren).

int m = B.length;
int[] array = new int[m];
for (int i=0,i<m;i++) {
  array[i] = A[ B[i] ];
}

EDIT: Vielleicht habe ich das Muster von B noch nicht verstanden.
Heisst B[0], dass das B[0]-te Element an die 0-te Stelle soll oder
heisst B[0], dass das 0-te Element an die B[0]-te Stelle soll?

 

[techdevil]

Ich hatte leider vergessen zu erwähnen, dass die Aufgabenstellung erfordert, dass man keine weiteren Arrays einführt, sondern nur die Arrays A und B benutzt.

EDIT:

Wenn B[0]=4 ist, dann bedeutet dass, das A'[4]=A[0]
Also der Wert von B beim Index 0 ist der Index des Wertes A[0] im neuen Array A'

 

[Mizar]

Hmmm... also ohne ein weiteres Array anzulegen und ohne das Muster-Array zu ändern fällt mir nur der folgende Weg mit Rekursion ein:

import java.util.Arrays;

public class MusterSortTest
{
	public static void arrayMusterSort(int[] array, int[] muster)
	{
		if(array.length == muster.length && array.length > 0) { 
			array[0] = rec(array, muster, 0);
		}
	}
	
	public static int rec(int[] array, int[] muster, int n)
	{
		int ret = array[muster[n] - 1];
		if(++n < array.length) {
			array[n] = rec(array, muster, n);
		}
		return ret;
	}
	
	public static void main(String[] args)
	{
		int[] A = new int[]{18, 4, 2, 7};
		int[] B = new int[]{4, 1, 3, 2};
		System.out.println("Vor Sortierung: " + Arrays.toString(A));
		arrayMusterSort(A, B);
		System.out.println("Nach Sortierung: " + Arrays.toString(A));
	}
}

Vielleicht fällt ja jemandem noch etwas anderes ein.

 

[techdevil]

Das funktioniert auf jeden Fall.
Aber geht es auch ohne Rekursion?
Wie würde es gehen wenn man das Muster-Array ändert?

 

[Mizar]

So zum Beispiel:

public static void arrayMusterSort2(int[] array, int[] muster)
{
	if(array.length != muster.length) {
		return;
	}
	for(int i = 0; i < muster.length; ++i) {
		muster[i] = array[muster[i] - 1];
	}
	for(int i = 0; i < muster.length; ++i) {
		array[i] = muster[i];
	}
}

Also werden hier die entsprechenden Werte einfach ins Muster-Array geschoben und anschließend in das eigentlich zu sortierende Array. Dabei wird eben wie gesagt das Muster-Array mit verändert, weshalb ich den rekursiven Weg bevorzugen würde, da dort das Muster-Array unangetastet bleibt. Wie man die Aufgabe aber ohne ein neues Array anzulegen und ohne das Muster-Array zu ändern ohne Rekursion schaffen soll, wäre mir persönlich ein Rätsel.

 

[javimka]

Das wird jetzt aber falsch permutiert, weil techdevil ja gesagt hat, dass wenn B[0]==4 ist, A'[4]=A[0] gelten soll. D.h., die Einträge m_i in Muster beschreiben, wo das Element i hin soll. Du machst das aber umgekehrt, nämlich so, dass die m_i beschreiben, welches Element an die Stelle i hin soll.

 

[techdevil]

ja das haste rechte javimka.
Was sagt ihr dazu:

import java.util.Arrays;

public class Aufgabe_4_Korrekt {
	   
	public static void main(String[] args) {
        int[] X = {88,66,77,11,55};
        int[] A = {1,3,2,5,4};
        X = Quicksort(A, X, 0, X.length-1);
        System.out.println(Arrays.toString(X));
    }
	
	public static int[] Quicksort(int[] a, int[] x, int l, int r){
        if (l<r) {
            int teiler = partition(a, x, l,r);
            Quicksort(a, x, l, teiler-1);
            Quicksort(a, x, teiler+1, r);
        }
        return x;
    }
   
    public static int partition(int[] a, int[] x, int l, int r){
        int i = l, j = r-1, pivot = a[r];
        do{
            while ((a[i] <= pivot) && (i<r)) i++;
            while ((a[j] >= pivot) && (j>l)) j--;
            if (i<j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                i++; j--;
            }
        } while (i<j);
        if (a[i]>pivot) {
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
            temp = x[i];
            x[i] = x[r];
            x[r] = temp;
        }
        return i;
    }
}

 

[javimka]

Da kommt bei mir [88, 77, 66, 55, 11] raus, was ja nicht stimmt. Das Array ist einfach abwärts sortiert, aber nicht gemäss Muster. Dann wäre die Lösung ja [11, 66, 55, 88, 77].
Methodennamen sollten klein geschrieben werden, also quicksort(), statt Quicksort.

 

[techdevil]

X = {88,66,77,11,55};
A = {1,3,2,5,4};

Also es sollte {88,77,66,55,11} rauskommen, da der Wert von A den Index von X im "neuen" Array angibt.
Das die Folge jetzt abwärts sortiert ist, ist Zufall.

 

[eRaaaa]

X = {88,66,77,11,55};
A = {1,3,2,5,4};

Also es sollte {88,77,66,55,11} rauskommen, da der Wert von A den Index von X im "neuen" Array angibt.

Dann sollte aber A korrekterweise auch bei 0 anfangen, nicht bei 1 :bae:

 

[javimka]

Achso, ich dachte, du musst das Array zuerst normal sortieren und erst dann die Positionen vertauschen. In dem Fall aber stimmt es wohl

 

[Mizar]

Hmm,... sicher das deine Quicksort()-Methode funktioniert? Weil ich habe diese mal mit den beiden Arrays aufgerufen, die du am Anfang des Threads angegeben hattest:
A= {18, 4, 2, 7} und B= {4, 1, 3, 2}
Und zwar:

public static void main(String[] args)
{
	int[] A = new int[]{18, 4, 2, 7};
	int[] B = new int[]{4, 1, 3, 2};
	System.out.println("Vor Sortierung: " + Arrays.toString(A));
	A = Quicksort(B, A, 0, A.length - 1);
	System.out.println("Nach Sortierung: " + Arrays.toString(A));
}

Als Ausgabe erhalte ich aber:

Vor Sortierung: [18, 4, 2, 7]
Nach Sortierung: [4, 7, 2, 18]

Aber ich dachte das Endergebnis müsste wie folgt lauten:

Nach Sortierung: [7, 18, 2, 4]

Vielleicht habe ich ja jetzt nen Denkfehler, oder es stimmt was mit der Methode nicht. :bahnhof:

 

[eRaaaa]

Nein, nach seiner Definition passt es. Auch mit seinem erwarteten Ergebnis aus Post #1 stimmt es überein

sodass am Ende A=4,7,2,18 ist

18 soll an Stelle 4
4 an 1
2 an 3
7 an 2

(mal davon abgesehen dass der Index eig. bei 0 beginnt)

 

[Mizar]

Achso, stimmt es steht ja sogar in seinem 1. Post:

Gesucht ist ein Sortieralgorithmus, sodass am Ende A=4,7,2,18 ist.

Man ich habe die ganze Zeit den Sortieralgorithmus nicht geschnallt.

 

[Sonecc]

ich will ja nix sagen, aber in der aufgabe wird gefordert, dass die funktion eine durchschnittliche Komplexität O(n logn) haben soll.
Quicksort hat allerdings nur im Best Case eine Komplexität von O(n logn)
Ich würde daher behaupten, dass Quicksort die falsche Wahl ist...

Edit: Uni Zeit ist zu lang her .. Könnte wohl richtig sein

 

[javimka]

Nein, da hast du schon Recht, im Worst Case läuft Quicksort in O(n^2)