BubbleSort

[kulturfenster]

Hallo allerseits,
Ich habe mich mit dem BubbleSort - Algorithmus versucht.

Hier ist meine Version:

public void sort(int[] a)
	{
		
		for(int j = 0; j < a.length; j++)
		{
			for(int i = 0; i < a.length-1; i++)
			{
				if(a[i] > a[i+1])
				{
					int x = a[i+1];
					a[i+1] = a[i];
					a[i] = x;
				}
			}
		}
	}

Meine Frage nun: Wie kann ich die Laufzeit testen? In der mainMethode lasse ich mir die Zeitdifferenz ausgeben, aber die Millisekunden helfen mir natürlich auch nicht weiter. Wenn ich mich richtig erinnere liegt die Laufzeit des BubbleSort zwischen n² und nlog(n). Stimmt es, dass die Dauer der Sortierung bei 1000 Elementen also zwischen 3000 und 1'000'000 Millisekunden liegt? Mein Wert liegt leider deutlich darunter, weshalb ich wohl irgendwo einen Denkfehler gemacht habe.

andere Frage: Wenn ich der sort-Methode einen bereits sortierten Array übergebe, ist die Laufzeit nicht konstant. Woran liegt das?

Vielen Dank für Tipps und Hilfen!

 

[Roar]

Mein Wert liegt leider deutlich darunter, weshalb ich wohl irgendwo einen Denkfehler gemacht habe.

ja, die laufzeit O hat nichts mit der ausführungszeit des codes auf deinem rechner zu tun, wär ja noch schöner wenn bubblesort auf meinem supercomputer ne geringere 'laufzeit' hat als bei dir

 

[kulturfenster]

stimmt, verstehe.

Wie kann ich nun aber meinen Algo testen?

 

[SlaterB]

teste mit n= 1000 und n = 5000

wenn's bei 5-fachen n 25x so lange dauert, dann ist es quadratisch


(wenn n=1000 zu schnell ist, dann suche dir eine Zahl bei der es ~1 sek dauert und ver-x-fache dann)

 

[kulturfenster]

ok, danke. Quadratisch scheints nicht zu sein.

Noch wegen vorhin: Wieso ist die Laufzeit bei einer geordneten Liste nicht kostant??

Und noch was anderes:

public void sort2(int n, int[] a)
	{
		if(n == a.length-1) return;
		else {
			if(a[n] > a[n+1]){
				int x = a[n+1];
				a[n+1] = a[n];
				a[n] = x;
			}
			sort2(n+1, a);
		}
	}

Dies ergibt leider ab ca. 1000 Elementen einen StackOverFlow? Wie kann ich den umgehen?

 

[SlaterB]

ganz einfach: hör auf, das rekursiv zu machen

> Noch wegen vorhin: Wieso ist die Laufzeit bei einer geordneten Liste nicht kostant??

auf was bezieht sich 'vorhin'?
und wieso konstant? muss nicht jedes Element wenigstens einmal angeschaut werden?

 

[kulturfenster]

ganz einfach: hör auf, das rekursiv zu machen icon_wink.gif

Wie weiss ich dann, wann ich von Rekursion Gebrauch machen soll? Einfach ausprobieren und wenns nicht funktioniert, sein lassen?

und wieso konstant? muss nicht jedes Element wenigstens einmal angeschaut werden?

Doch, klar. Aber angenommen, ich habe einen Array mit 5 Elementen, a = {1,2,3,4,5}.
So werden 4 Vergleichsoperationen (a < a[i+1]), die allesamt true ergeben, durchgeführt. Wenn ich das mehrmals durchlaufen lasse, sollte es doch immer gleich lange dauern, also konstant sein!?

 

[SlaterB]

ja, sollte dann konstant sein, +-100ms musst du aber immer einrechnen,
das ist normale Ungenauigkeit/ andere Systemprozesse und ähnliches

evtl. wird beim ersten Durchlauf auch Speicher belegt oder ähnliches,
10 Durchläufe liefern bessere Vergleichszahlen, alles was unter 1 Sec dauert ist eh zu kurz

> Wie weiss ich dann, wann ich von Rekursion Gebrauch machen soll?

na hier ist doch offensichtlich, dass die Rekursionstiefe genau n entspricht,
um im Tausender-Bereich ist Rekursion generell gefährlich

viel mehr Spass hast du z.B. bei einem Sortieralgorithmus Divide & Conquer im logarithimischen Maß, z.B. mit Intervallhalbierung,

da brauchst du bei 1000 Elementen nur eine Tiefe ~10
(1000, 500, 250, 125, 60, 30,15,7,3,..)

bis du da bei über 100 Intervallhalbierung bist ist dein Speicher eh voll, da ist der StackTrace sicher