Vergleiche und Vertauschungen |
| 23.11.2007, 13:51 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | 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. |
||
|
|
|||
| 27.11.2007, 15:12 | Auf diesen Beitrag antworten » | ||
| Tobias | Ja, stimmt. Das einzige, was mich stört ist
Warum da am Ende (n-1) und nicht (n-3) ? |
||
| 27.11.2007, 15:39 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | 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 
|
||
|
|