Zum Inhalt springen
View in the app

A better way to browse. Learn more.

Fachinformatiker.de

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

Sortieren

Empfohlene Antworten

Veröffentlicht

hallo haben uns mit sortieren und suchen beschäftigt, habe nun eine frage:

selection sort (also sortieren durch auswahl) ist nicht abhängig von der ausgangsreihenfolge der zu sortierenden elemnte.

aber warum ist das so?

selection sort (also sortieren durch auswahl) ist nicht abhängig von der ausgangsreihenfolge der zu sortierenden elemnte.
Du meinst vermutlich, dass die Laufzeitkomplexität von Selection Sort davon unabhängig ist.

aber warum ist das so?
Der Algorithmus profitiert nicht von einer Vorsortierung, weil er in jedem Schritt immer alle verbliebenen unsortierten Elemente durchsuchen muss, um das jeweils nächste kleinste zu finden. Es gibt da keine Möglichkeit, die Suche vorzeitig abzubrechen. Die Anzahl der Vergleiche, die bei Selection Sort stattfinden, ist immer gleich.

also ich meinte die anzahl von vergleichen beim sortieren durch auswahl

und wenn ich weiss, dass die zu sortierende liste schon fast sortiert ist, d.h. noch wenige ausnahmen,

dann würde ich mich für insertion sort, d.h. sortieren durch einfügen entscheiden, weil doch dieser sortieralgorithmus stabil ist, d.h. die reihenfolge der datensätze, der schlüssel gleich ist nicht verändert wird und der aufwand dann nicht so groß ist weil die liste schon sortiert ist.

kann man das so sagen???

und wenn ich weiss, dass die zu sortierende liste schon fast sortiert ist, d.h. noch wenige ausnahmen,

dann würde ich mich für insertion sort, d.h. sortieren durch einfügen entscheiden, weil doch dieser sortieralgorithmus stabil ist, d.h. die reihenfolge der datensätze, der schlüssel gleich ist nicht verändert wird und der aufwand dann nicht so groß ist weil die liste schon sortiert ist.

Die erste Begründung ist Unsinn. Wenn du einen stabilen Sortieralgorithmus brauchst, musst du einen stabilen Sortieralgorithmus verwenden, das hat nichts damit zu tun, ob die Folge vorsortiert ist.

Die zweite Begründung passt schon eher. Allerdings benutzt man in der Praxis Selection Sort und Insertion Sort nur für kleine Listen, weil sie O(n^2) haben. Bei größeren Listen benutzt man dann einen der Algorithmen mit O(n log n), wie Quicksort oder Mergesort.

ach so ok,

also wenn ich weiss das die liste schon fast sortiert ist, also bis auf wenige elemente, dann könnte ich theoretisch insertion sort anwenden, jetzt im allgemeinem fall.

danke

also wenn ich weiss das die liste schon fast sortiert ist, also bis auf wenige elemente, dann könnte ich theoretisch insertion sort anwenden, jetzt im allgemeinem fall.
Theoretisch kannst du Insertion Sort immer anwenden. Alle Sortieralgorithmen erfüllen ihren Zweck.

Wenn es um die Wahl eines bestimmten Algorithmus geht, ist eine Vorsortierung nur ein Kriterium von vielen. Wichtig ist unter Anderem auch, ob du einen stabilen Algorithmus brauchst, wie groß das zu sortierende Feld ist, wie teuer ein Vergleich in Relation zu einer Vertauschung ist usw.

  • 8 Monate später...
Bei größeren Listen benutzt man dann einen der Algorithmen mit O(n log n), wie Quicksort oder Mergesort.

Quicksort hat allerdings ein schlechtes Worst-Case Verhalten ( O(n²) ), daher besser Mergesort oder Heapsort...

Archiv

Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.