---

Geschrieben von JROppenheimer am 23.11.2007 um 13:51:

  Vergleiche und Vertauschungen

Gegeben ist eine Folge [n, n-1, 1, 2, 3, ... ,n-2]

Ich will asymptotisch genau die Anzahl der Vergleiche und der Vertauschungen für die Alg. BubbleSort, Select.Sort und Insert.Sort bestimmen.

Jetz hab ich mir das so gedacht:

BubbleSort läuft 3 mal durch. das erstemal läuft das Element n bis ans Ende der Folge, das zweite mal läuft das Element n-1 bis an die vorletzte Stelle der Folge und beim dritten durchlauf wird gar nicht mehr getauscht, sondern nur noch verglichen.

Das heißt: Anzahl der Vergleiche ist (n-1)+(n-2)+(n-1) ist in Theta(n)
Anzahl der Vertauscungen ist (n-1)+(n-1) ist in Theta(n)

ist das richtig?

Bei Selection Sort dachte ich mir: Vergleiche sind Theta(n^2) und Vertauschungen sind Theta(n)

und bei Insertionsort komme ich auch auf das selbe wie bei Selectionsort.

---

Geschrieben von Tobias am 27.11.2007 um 15:12:

 

Ja, stimmt.

Das einzige, was mich stört ist

Zitat:

Das heißt: Anzahl der Vergleiche ist (n-1)+(n-2)+(n-1) ist in Theta(n)

Warum da am Ende (n-1) und nicht (n-3) ?

---

Geschrieben von JROppenheimer am 27.11.2007 um 15:39:

 

danke, Du bist der beste!!!!

ich weiss auch net, warum ich da wieder n-1 hingeschrieben hab. Ich hatte schon ne weile dran rumgemurkst, als ich das hier gepostet habe und eigendlich auf immer n-3 am ende stehen gehabt,...

aber dann dachte ich mir irgendwie, beim letzten durchlauf testet er noch mal alle elemente, um dann die abbruchbedingung zu "erfüllen" oder so ähnlich. Aber das muss er ja nicht mehr, weil er ja vorher schon 2 Elemente nach hinten geschoben hat, und somit nur noch die n-2 Elemente vergleichen muss, was n-3 Vergleiche erfordert.

wenn man zulange auf sowas glotzt, dann wird man irgendwann komisch im kopp