# Bubble-Sort worst case optimieren...



## DerGroßeNargus (17. Jan 2011)

Hi,

ich habe folgenden Code zu Bubble-Sort gegeben. (Es gibt eine aufsteigend sortierte Liste wieder)


```
private static void sort(int[] m) {
	
		int n = m.length;
		boolean done = false;
		
		for(int j = 0; j < n && !done; ++j) {
			done = true;
			for(int i = 0; i < n-1 ; ++i) {
				
				if (m[i] > m[i+1]) {
					
					int temp = m[i];
					m[i] = m[i+1];
					m[i+1] = temp;
					done = false;
					
				}
			}
		}
	}
```

Der Code in der inneren der beiden for-Schleifen wird im worst-case n*(n-1) mal durchlaufen (n = length des zu sortierenden arrays m). 
Worst-case wäre: falschrum sortiertes array zB. 8,7,6,5,4,3,2,1,0 dann werden n*(n-1) = 72 durchläufe gebraucht.

Ich soll nun eine V_erbesserung an obigen Code aber in nur einer Zeile _(!) vornehmen, damit sich die _Anzahl der Durchläufe im worst-case auf n*(n-1)/2 reduzieren_.
Könnt ihr mir sagen, was ich wie verändern muss? Ich bin ziemlich ratlos und habe schon sehr viel auch mit output und Zählvariablen ausprobiert...

Vielen Dank für eure Hilfe!


----------



## SlaterB (17. Jan 2011)

> Optimizing bubble sort
> 
> The bubble sort algorithm can be easily optimized by observing that the largest elements are placed in their final position in the first passes. Or, more generally, after every pass, all elements after the last swap are sorted, and do not need to be checked again. This not only allows us to skip over a lot of the elements, but also skip tracking of the "swapped" variable. This results in about a worst case 50% improvement in iteration count, but no improvement in swap counts.


Bubble sort - Wikipedia, the free encyclopedia

das dort angegebene ist in einer Zeile kaum zu machen, aber es dürfte schon reichen, die innere Schleife immer um 1 zu kürzen,
[c]for(int i = 0; i < n-1; ++i) {[/c]
[c]for(int i = 0; i < n-1-j; ++i) {[/c]
oder so

edit:
wobei sich das nur Anzahl Vergleiche bezieht, die ist eigentlich immer n*(n-1), auch im Best Case..,
auf die Anzahl Vertauschungen wirkt sich das nicht aus, insofern vielleicht nicht richtig für deine Aufgabe und auch im Wiki etwas komisch,
wenn ich das nicht ganz falsch verstehe

andererseits:


> Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted.


warum dann aber so auf worst-case geschaut wird..

ach so, im Best Case reicht ein Durchgang, dann wird schon aufgehört, O(n),
dann passt es glaube ich 
(bei Halbierung der Schritte ist die Komplexität immer noch O(n2))


----------



## DerGroßeNargus (17. Jan 2011)

```
for(int j = 0; j < n && !done; ++j) {
```

ersetzt durch


```
while(!done) {
```

ist denke ich die Lösung... was meinst du?

Edith wollte noch anfügen, dass die deutsche wikipedia bei diesem Problem sehr leicht in die Irre führen kann... Die beschreibung, wo dieses n*(n-1)/2 auftaucht ist nicht wirklich optimal ausgedrückt...


----------



## SlaterB (17. Jan 2011)

siehe auch meine edits im ersten Posting,
und nein, ich denke nicht, wobei du das auch selber testen kannst mit zählen und es dafür nicht wirklich einen Grund gibt, ansonsten nennen


----------



## SlaterB (18. Jan 2011)

im deutschen Wikipedia wird die 50% Optimierung gar nicht extra erwähnt, sondern schon bei der ersten Implementierung eingebaut,


> Der obige Schritt wird solange wiederholt, bis die Reihe komplett sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs aber nicht mehr betrachtet werden, da es seine endgültige Position schon gefunden hat.




darunter zur Komplexitätsberechnung kommt zwar n*(n-1)/2 vor, aber nicht explizit deswegen


----------



## DerGroßeNargus (18. Jan 2011)

Ich glaub ich hab mich geirrt. Das ändert nichts....


----------



## DerGroßeNargus (18. Jan 2011)

Noch eine Idee? ???:L


----------



## SlaterB (18. Jan 2011)

die aus meinem ersten Post ist sicherlich die gesuchte


----------



## DerGroßeNargus (18. Jan 2011)

```
...
		for(int j = 0; j < n && !done; ++j) {
			
			done = true;
			for(int i = 0; i < n-1 ; ++i) { 
				///------ hier waren es 72 durchläufe bei n = 9 , wegen n*(n-1) im worst case
				if (m[i] > m[i+1]) {
			
					int temp = m[i];
...
```

und jetzt kommt die sau dumme verzweifelte Lösung:


```
...
		for(int j = 0; j < n && !done; ++j) {
			
			done = true;
			for(int i = 0; i < n-1 && m[i] > m[i+1]; ++i) { 
				///------ hier sind es jetzt nur noch 36 durchläufe! bei n = 9 im worst case das entspricht n*(n-1)/2 
				if (m[i] > m[i+1]) {
			
					int temp = m[i];
...
```

aber wenn das wirklich so gemeint war..... meine güte >_<

Aber es erfüllt die Aufgabe: 
Die mit ///----- markierte Stelle wird im worst-case n*(n-1) Mal durchlaufen, wobei n die Länge der Reihung m ist. Welche Verbesserung müsste an obiger Funktion vorgenommen werden, um die Anzahl der Durchläufe im worst-case auf n*(n-1)/2 zu reduzieren? Es darf hierfür nur genau eine Zeile verändert werden!


----------



## SlaterB (18. Jan 2011)

für das Worst-Case-Beispiel funktioniert deine Lösung, aber es ist doch leicht zu erkennen, dass das allgemein übel ist,
wenn das Array 7, 8, 6, 5, 4, 3, 2, 1, 0 lautet, dann wird schon ganz am Anfang abgebrochen, das Array nicht sortiert,

Code zu wiederholen, wie diesen komplizierten Vergleich aus dem if, ist selten eine gute Lösung,

ich verstehe nicht wieso du dich gegen die Lösung aus meiner ersten Antwort sträubst, 
nur 2-3 Zeichen einfache Änderung auch mit gewünschten Ergebnis,
in Wikipedia bestätigt also offiziell bekannt, mehr kann man sich doch nicht wünschen


----------



## DerGroßeNargus (18. Jan 2011)

Deine Lösung ist die bessere. Vielen Dank!


----------

