---

Geschrieben von coooo am 20.05.2015 um 20:56:

  Komplexität (Bubblesort)?

Hallo,

habe folgende Aufgabe vor mir liegen & weiß nicht, ob es sich hierbei um ein Bubblesort handelt bzw. wie man die Aufgabe lösen könnte.

Hat jemand eine Idee?

---

Geschrieben von eulerscheZahl am 20.05.2015 um 21:35:

 

Ein Stichwort: Insertionsort.

---

Geschrieben von Tina92 am 22.05.2015 um 17:40:

 

Hallo,

mal eine Frage zu den ganzen Sortieralgorithmen. Warum brauche ich denn so viele verschiedene? MergeSort, InsertionSort, BubbleSort usw.

---

Geschrieben von eulerscheZahl am 22.05.2015 um 17:46:

 

Zum einen, weil die einen komplizierter sind als die anderen, zum anderen weil sie unterschiedliche Eigenschaften haben.

Einen Bubblesort kann man sich in 5 Minuten ausdenken (und für Studenten ist er auch am leichtesten zu verstehen). Quicksort gibt "erst" seit 1960.
Quicksort arbeitet im Normalfall in O(n*log(n)), kann aber auch O(n^2) haben, wenn die Liste in umgekehrter Reihenfolge sortiert ist. Mergesort ist immer O(n*log(n)), braucht aber zusätzlichen Speicher. Da muss man eben zwischen Laufzeit uns Speicherbedarf abwägen.

---

Geschrieben von Tina92 am 23.05.2015 um 17:58:

 

Danke für die Antwort.

Zitat:

Quicksort arbeitet im Normalfall in O(n*log(n)), kann aber auch O(n^2) haben, wenn die Liste in umgekehrter Reihenfolge sortiert ist. Mergesort ist immer O(n*log(n)), braucht aber zusätzlichen Speicher. Da muss man eben zwischen Laufzeit uns Speicherbedarf abwägen.

Wo weißt du denn die ganzen Komplexitäten her? Sprich O(n*log(n)) usw.?

---

Geschrieben von eulerscheZahl am 23.05.2015 um 18:00:

 

Das kann man nachlesen oder sich mit ein wenig Aufwand auch selbst herleiten. Bei den gängigen Algorithmen weiß man das auch recht schnell auswendig.

---

Geschrieben von Tina92 am 23.05.2015 um 18:15:

 

Achso, ich war immer der Meinung, dass das für jeden Code unterschiedlich ist :-)

---

Geschrieben von coooo am 09.06.2015 um 22:32:

 

Wieso ist es Insertion Sort? Beim Instertion Sort wird doch nicht nach Minimum und Maximum gesucht.

---

Geschrieben von eulerscheZahl am 10.06.2015 um 15:38:

 

Beim in der Aufgabenstellung beschriebenen Algorithmus ja auch nicht.