divide

[heppi75]

hallo,

wieder mal ein problem mit einer aufgabe - pivot element (p) = letztes Element.

ich soll folgende liste: 9, 16, 17, 5, 3, 18, 14, 4, 14, 17
mit divide in folgende form bringen: 9, 16, 14, 5, 3, 4, 14, 17, 17, 18
ich komme aber immer auf: 9, 16, 3, 5, 4, 14, 14, 17, 17, 18

bitte hilfe!

public static int divide(int[] list, int leftIdx, int rightIdx)
    {
	if (leftIdx < 0 || rightIdx < 0 || leftIdx > list.length - 1 || rightIdx > list.length - 1)
	    throw new IllegalArgumentException();

	int p = list[rightIdx];

	for (int i = 0; i < list.length - 1; i++)
	    if (list[i] >= p)
		for (int j = list.length - 1; j > i; j--)
		    if (list[j] < list[i])
			swap(list, i, j);

	return p;
    }

    public static void swap(int[] list, int i, int j)
    {
	if (i < 0 || j < 0 || i > list.length - 1 || j > list.length - 1)
	    throw new IllegalArgumentException();

	int temp = list[i];
	list[i] = list[j];
	list[j] = temp;
    }

 

[Firephoenix]

Was genau soll denn der Algorythmus machen?
Von
9, 16, 17, 5, 3, 18, 14, 4, 14, 17
nach
9, 16, 14, 5, 3, 4, 14, 17, 17, 18
erschließt sich mir nicht.

Pivot und das tauschen sieht irgendwie nach Quicksort aus, aber die erwartete Liste ist definitiv nicht sortiert

Gruß

 

[heppi75]

also die aufgabe lautet:

pivot element = letztes Element

2 listenteile erstellen, list wie folgt umstellen: zuerst beinhaltet list alle Elemente die kleiner als unser Pivot-Element sind. dann kommt das pivot element und rechts davon alle elmente die grösser oder gleich sind. innerhalb der teile muss keine sortierung vorliegen.

rückgabe der position des pivot-elements innerhalb der liste. die position für dieses element ändert sich im verlauf des algorithmus nicht mehr ...

 

[pl4gu33]

hallo,

wieder mal ein problem mit einer aufgabe - pivot element (p) = letztes Element.

ich soll folgende liste: 9, 16, 17, 5, 3, 18, 14, 4, 14, 17
mit divide in folgende form bringen: 9, 16, 14, 5, 3, 4, 14, 17, 17, 18
ich komme aber immer auf: 9, 16, 3, 5, 4, 14, 14, 17, 17, 18

bitte hilfe!

also deine Ausgabe ist nach der Aufgabenstellung doch ebenfalls richtig, da die Sortierung innerhalb ja nicht zählt....

wenn du deine Methode mit der List 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 aufrufst und dann über die volle Länge gehst dann ist das Ergebnis von "9, 16, 3, 5, 4, 14, 14, 17, 17, 18" doch genauso richtig, wie "9, 16, 14, 5, 3, 4, 14, 17, 17, 18" mit dem Pivot- Element 17

 

[Sesostris]

Grundsätzlich stimme ich pl4gu33 zu, dass deine Ausgabe richtig ist. Jedoch hat dein divide noch einige grobe Fehler, die dir spätestens dann zum Verhängnis werden, wenn du damit einen Quicksort schreiben willst.
Da wäre das "list.length", das in divide nichts verloren hat. Du darfst lediglich den Bereich zwischen leftIdx und rightIdx betrachten. Auch solltest du dir überlegen, ob es wirklich zwei verschachtelte Schleifen sein müssen. Zur Erinnerung: Quicksort hat eine Laufzeitkomplexität von O(n*log(n)). Dein divide ist bereits in O(n^2). Außerdem gibt dein divide nicht die Position des Pivots zurück, sondern das Pivot selbst.