Komisches Java im Script

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Komisches Java im Script
Also ich hab mal aus Langeweile und zur Übung die ganzen Sortierverfahren selber in Java implementiert, und musste feststellen dass z.b. die AddAll methode aus Kapitel 14.5 überhaupt nicht funktioniert.

Sehr viel von den Iteratoren Schleifenkram geht nicht wirklich und enthält viele Bugs.

Ist das noch jemanden aufgefallen oder bin ich der einzige der sich die Mühe gemacht hat das zu überprüfen? :slight_smile:

Wenn man zum Beispiel 2 Mengen hat eine mit {2,8} die andere mit {5,6} ergibt der Code aus dem Script {2,8,5,6} raus etc pp.

(code wurde eins zu eins übernommen)

Funktion wird aufgerufen mit
merge({2,8},{5,6}) //pseudo code, die dinger müssen natürlich LL sein


static LinkedList merge(LinkedList l1, LinkedList l2) {

		ListIterator i = l1.listIterator();
		ListIterator j = l2.listIterator();
		while (i.hasNext() && j.hasNext()) {
			Object a1 = i.next();
			Object a2 = j.next();

			while (((Comparable) a1).compareTo((Comparable) a2) <= 0
					&& i.hasNext()) {
				a1 = i.next();
			}
			if (i.hasNext())
				i.previous();
			i.add(a2);

		}

		while (j.hasNext())
			i.add(j.next());

		return l1;
	}

Der Iterator geht nun weiter und befindet sich auf 8, da dies die erste Zahl aus l1 ist, die größer als 5 ist. Der If Ausdruck überprüft ob nach 8 noch was kommt. Dies is nicht der Fall, daher wird nicht zurückgesprungen und die 5 wird ans Ende der Liste gehängt, was natürlich nicht sein darf. Beim nächsten durchlauf, steht a1 jetzt auf der so eben hinzugefügten “5” und das gleiche passiert wieder. Das “sortierte” Ergebnis laut Vorlesungs code ist also:

2 8 5 6

Und das finde ich nicht so toll. :vogel:


Und so würde es funktionieren:

	LinkedList merge(LinkedList l1, LinkedList l2) {

		ListIterator i = l1.listIterator();
		ListIterator j = l2.listIterator();

		Object a1 = i.next();
		Object a2;
		do {
			a2 = j.next();

			while (((Comparable) a1).compareTo((Comparable) a2) <= 0
					&& i.hasNext()) {
				a1 = i.next();
			}
			if (((Comparable) a1).compareTo((Comparable) a2) >= 0) {
				i.previous();
				i.add(a2);
				i.next();
			} else {
				i.add(a2);
			}

		} while (j.hasNext());

		return l1;
	}

Tja…dann gibt es zwei möglichkeiten:

Entweder der Urheber des Codes oder Du darf sich demnächst offiziel “Nub” taufen lassen :smiley:

Mal sehen auf wen das dann zutrifft :slight_smile:


Der im Script beschriebene Code für Quicksort funktioniert auch nicht. Die Sortierung ums Pivotelement wird nicht ganz ausgeführt, das letzte Element wird nicht verschoben, ausserdem wird der “swap” befehl auch mit 2 gleichen Zahlen ausgeführt. (Tausche 1 mit 1)

Hier meine reparierte Funktion:


import java.util.LinkedList;

class quicksort {
	LinkedList m;

	quicksort(LinkedList t) {
		m = t;
	}

	void sort() {
	 	for (int i = 0; i <= m.size() - 1; i++) {
			System.out.print(m.get(i) + " ");
		}
		System.out.println();
     quicksortRec(0,m.size()-1);

	}

	void quicksortRec (int start, int end) {
		if (end > start) {
			

			
		Object p = m.get((start+end)/2);
		
		int i = partition(start,end,p);
		quicksortRec(start,i-1);
		quicksortRec(i,end);
		}
	}
	
	int partition (int start, int end,Object p) {
		
		while (start <= end) {
			while ((start <= end) && ( ((Comparable) m.get(start)) .compareTo(p) < 0 )) {
				start++;
			}
			while ((start <= end) && ( ((Comparable) m.get(end)) .compareTo(p) > 0 )) {
				end--;
			}
			if (start < end) {
				Object h1 = m.get(start);
				Object h2 = m.get(end);
				
				System.out.println("Tausche " + h1 + " und " + h2 + " für PivotElement " + p );
				
				m.remove(start);
				m.add(start,h2);
				
				m.remove(end);
			    m.add(end,h1);
			    
				 
			    if (m.get(end) != p)  end--;
				
				
				for (int i = 0; i <= m.size() - 1; i++) {
					System.out.print(m.get(i) + " ");
				}
				System.out.println();
				
			}
			start++;
		}
		
		return start;
		
	}
	public static void main(String args[]) {

		LinkedList g = new LinkedList();

		g.add(new Integer(10));
		g.add(new Integer(3));
		g.add(new Integer(2));
		g.add(new Integer(5));
		g.add(new Integer(8));
		g.add(new Integer(1));
		g.add(new Integer(4));
		g.add(new Integer(7));
		
		quicksort L = new quicksort(g);
		L.sort();
	}
}