Komplexität Algorithmus

Ah die Basis des Logarithmus ist egal. Hängt wohl damit zusammen dass
es immer ein konstanter Vorfaktor ist, um den sich die Logarithmen unterscheiden. Mehr weiß ich allerdings auch nicht.

JaykopX

@HurgaHurga
sorry

lieg ich falsch oder wie soll ich das verstehn

Was mich auch noch intressiert. Beim Bubble Sort soll der best case O(n) sein.
Aber ich kenn keinen Algorithmus der bei der vorsortierten Liste dies
erkennt und dann abbricht.

JaykopX schrieb:

@HurgaHurga
sorry
->http://de.wikipedia.org/wiki/Asperger-Syndrom

Ich mache dir keinen Vorwurf, dass du nicht im Geringsten verstanden hast, was blurry333 mit der Frage meint, denn er vergisst den Zusammenhang zu erwähnen und die Notation ist auch nicht hilfreich.

Wenn du allerdings aus einem einfachen 3-Zeiler durch seltsame Substitutionsmechanismen einen 6-Zeiler mit Nonsens-Ergebnis machst musst du dir schon etwas Kritik gefallen lassen. Und ein Link auf die Schildbürger schien mir nicht so hart wie das eigentlich angebrachte Dieter Nuhr Zitat.

otze

klar, bubble sort geht einmal durch. ist die liste sortiert, wird auf dem Weg keine Vertauschung mehr durchgeführt und damit kann sofort abgebrochen werden.

Hier mal eine Implementierung aus dem Internet.

Die innere Schleife wird doch auch durchlaufen wenn das Array sortiert ist.

void bubbleSort(int *array,int length)//Bubble sort function 
{
	int i,j;
	for(i=0;i<10;i++)
	{
	   for(j=0;j<i;j++)
	    {
	      if(array[i]>array[j])
		{
		   int temp=array[i]; //swap 
		   array[i]=array[j];
		   array[j]=temp;
		}

	    }

	}

}

dir fehlt die flag ob eine vertauschung statt gefunden hat

prozedur bubbleSort( A : Liste sortierbarer Elemente ) 
  n := Länge( A )
  wiederhole
    vertauscht := falsch
    für jedes i von 1 bis n - 1 wiederhole 
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      ende falls
    ende für
    n := n - 1
  solange vertauscht und n >= 1
prozedur ende

lg lolo

Ah danke. Aber in der klassischen Variante war der best und worst case
immer O(n^2). Mit Flag ist er schneller als Quicksort

blurry625 schrieb:

Ah danke. Aber in der klassischen Variante war der best und worst case
immer O(n^2). Mit Flag ist er schneller als Quicksort

Aber doch auch nur im Best Case oder?

ja wenn es gut sortiert ist