 Vergleiche und Vertauschungen |
|
|
| 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.
__________________
I'm 71% Megatron!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von JROppenheimer: 23.11.2007 13:59.
|
|
23.11.2007 13:51 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
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) ?
|
|
|
27.11.2007 15:12 |
|
|
|
|
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 
__________________
I'm 71% Megatron!
|
|
|
27.11.2007 15:39 |
|
|
|
