0 Daumen
309 Aufrufe

Aufgabe:

Seien \( A \) und \( B \) zwei Umordnungen der Liste \( [1, \ldots, n] \). Angenommen, es gilt \( \operatorname{runs}(A)<\operatorname{runs}(B) \). Braucht dann der InsertionSort-Algorithmus für \( A \) weniger Bewegungen als für \( B \) ?

Avatar von

1 Antwort

0 Daumen

Es ist nicht sicher, dass der InsertionSort-Algorithmus für eine Umordnung mit weniger Runs weniger Bewegungen benötigt als für eine Umordnung mit mehr Runs.

Der InsertionSort-Algorithmus benötigt in jedem Schritt eine Bewegung für jedes Element, das nicht an der richtigen Position ist, unabhängig von der Anzahl der Runs.

Eine Umordnung mit weniger Runs kann dennoch mehr Bewegungen erfordern, wenn die Elemente weiter von ihren endgültigen Positionen entfernt sind.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community