Braucht dann der InsertionSort-Algorithmus für A weniger Bewegungen als für B?

Question

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 \) ?

Answer 1

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.