Vector sortieren nach Objekt-Info?

[soucy]

Ich habe einen Vector mit Personen aus einer Datenbank. Da die ID als PrimaryKey nur 1 mal vorhanen sein darf, würde ich den Vector gerne danach sortieren.

Nun habe ich mir eine Funktion geschrieben.

	private Vector<Person> Sort(Vector<Person> vec)
	{
		int i,j;
		Person tmp = new Person();
		Person p1 = new Person();
		Person p2 = new Person();
		for(i=0;i<vec.capacity()-1;i++)
		{
			for(j=0;j<vec.capacity()-i-1;j++)
			{
				p1 = vec.get(0);
				p2 = vec.get(2);
				if(Integer.valueOf(p1.getID()).intValue() >= Integer.valueOf(p1.getID()).intValue())
				{
					tmp = p1;
					p1 = p2;
					p2 = tmp;
					vec.remove(0);
					vec.add(0, p1);
					vec.remove(2);
					vec.add(2, p2);
				}
			}
		}
		return vec;
	}

Der Code hier funktioniert und tauscht mir das 1. (Pos. 0) mit dem 3. (Pos. 2) Element in der Liste.

Wenn ich jedoch anstatt der 0 j und anstatt der 2 ein j+1 einsetze, dann schmiert das Programm immer ab.

Kann mir jemand sagen wieso ich die Laufvariablen des BubbleSort hier nicht einsetzen kann? Das sind doch auch nichts anderes als Integer Werte

 

[André Uhres]

Ausser dem Bubblesort gibt's auch noch Collections.sort (mit Mergesort Algorithmus) und TreeSet.
Letzterer ist immer sortiert und eliminiert Doppelte automatisch.
Für die Alternativen muss Person einfach nur das Interface Comparable implementieren.
Btw: Bubblesort Beispiele findest du mit wenig Suche Haufenweise.

 

[SlaterB]

zur ursprünglichen Fehlersuche:

Tipp: wenn man sich mit dem Sortieralgorithmus noch nicht so sicher ist, dann testet man ihn idealerweise mit Strings und nicht komplizierten Person-Objekten,

dazu macht man sich einen Testvektor mit drei Elementen und noch die ein oder andere Zwischenausgabe,
man schaut sich Schritt für Schritt an, was eigentlich passiert

dann sag selbst: wie kann man nach diesen simplen Tricks den Fehler nicht selber finden? :

import java.util.Vector;

public class Test {

	public static void main(String[] args) throws Exception {
		Vector vec = new Vector();
		vec.add("h");
		vec.add("c");
		vec.add("e");
		p("vec: " + vec);
		new Test().sort(vec);
		p("vec: " + vec);
	}

	public Vector sort(Vector vec) {
		int i, j;
		String s1 = null; // besser mit null initialisieren 
		String s2 = null;

		for (i = 0; i < vec.capacity() - 1; i++) {
			for (j = 0; j < vec.capacity() - i - 1; j++) {
				int a = j;
				int b = j + 1;
				p("a: "+a+" - b: "+b+" j: "+j+" Maximum für j: "+(vec.capacity() - i - 1));
				s1 = (String) vec.get(a);
				s2 = (String) vec.get(b);
				if (s1.compareTo(s2) > 0) {
					p("tausche s1: "+s1+" ("+a+") mit "+s2+" ("+b+")");
					vec.remove(a);
					vec.add(a, s2); 
					vec.remove(b);
					vec.add(b, s1);
					p("vec: "+vec);
				}
			}
		}
		return vec;
	}

	public static void p(String st) {
		System.out.println(st);
	}
}

 

[Beni]

Und wenn man einen etwas schnelleren Algorithmus haben will, verwendet man einfach "Collections.sort" :wink:

 

[soucy]

Ich glaube ich sollte nach einer gewissen Zeit eine Programmierpause einlegen. Denn sonst wird man leicht Fehlerblind.

Heute morgen an den Code gesetzt und in 2 Min warn die Fehler korrigiert.

Zum einen muss ich .size() und nicht .capacity() benutzen und zum anderen habe ich bei der IF Abfrage auf beiden Seiten den String von P1 geholt

Trotzdem danke für eure Tipps.

 

[thE_29]

@Beni: weißt du eigentlich welcher Sort das ist?

Habe mir den QuickSort nachgeschrieben und sortiere dann immer übers compareable Interface!

Geht auch ruckzuck im Vergleich zum BubbleSort!

 

[Beni]

Klar weiss ich das the_29 - es steht ja in der API :bae:

Es ist ein leicht erweiterter Mergesort, also mit schlechtester Laufzeit O( n log n ) wenn ich mich nicht irre.

 

[Leroy42]

@Beni: weißt du eigentlich welcher Sort das ist?

Ein verfeinerter Merge-Sort!.

Ich hab' mal versucht ihn im Eclipse-Debugger zu analysieren :autsch:

==> Ich begnüge mich lieber damit die reinen Versionen der bekannten
Sortieralgorithmen zu verstehen.

Geht auch ruckzuck im Vergleich zum BubbleSort!

Bei den heutigen Rechnerleistungen gehen alle O(n*log n) Sortieralgorithmen ruckzuck.

Um überhaupt Unterschiede feststellen zu können, mußt du schon ein paar Millionen Werte
ein paar tausend mal sortieren um die Auflösung von System.currentTimeMillis zu umgehen.

Aber vorsicht: Die Zeiten für die Neuerzeugungen des unsortierten Arrays müssen
natürlich rausgerechnet werden. :meld:

 

[thE_29]

Mist, der Mergesort ist meinem Quicksort überlegen! ( worst cat O(n²))

Mhm.. Könnte ich ja den Mergesort einbauen wenns mir mal fad ist :bae:

 

[Leroy42]

...wenn ich mich nicht irre.

Bei Nicht-Standardfragen scheinst du dich tatsächlich nicht zu irren. :bae: