Komplexität (Bubblesort)? |
coooo
Jungspund
Dabei seit: 01.02.2015
Beiträge: 22
|
|
|
20.05.2015 20:56 |
|
|
Tina92 unregistriert
|
|
Hallo,
mal eine Frage zu den ganzen Sortieralgorithmen. Warum brauche ich denn so viele verschiedene? MergeSort, InsertionSort, BubbleSort usw.
|
|
22.05.2015 17:40 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
22.05.2015 17:46 |
|
|
Tina92 unregistriert
|
|
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.?
|
|
23.05.2015 17:58 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
23.05.2015 18:00 |
|
|
Tina92 unregistriert
|
|
Achso, ich war immer der Meinung, dass das für jeden Code unterschiedlich ist :-)
|
|
23.05.2015 18:15 |
|
|
coooo
Jungspund
Dabei seit: 01.02.2015
Beiträge: 22
|
|
Wieso ist es Insertion Sort? Beim Instertion Sort wird doch nicht nach Minimum und Maximum gesucht.
|
|
09.06.2015 22:32 |
|
|
|