Ist der folgende Algorithmus stabil?

Question

Dieser Algorithmus ist stabil oder nicht? Ich habe die Bedeutung von stable überprüft und etwas auf dieser Seite gefunden. Wenn ich richtig verstanden habe, ist etwas (wir sprechen über Sortieralgorithmen) stabil, wenn 2 Dinge mit gleichen Schlüsseln in der Reihenfolge in der Eingabe erscheinen, aber auch in der Ausgabe, die sortiert ist.

Der folgende Algorithmus ist der bekannte Bubblesort. Ich würde sagen, es ist stabil, weil ich nicht sehen kann, dass 2 gleiche Elemente jemals dort ausgetauscht werden, also muss es stabiler Algorithmus sein. Habe ich recht und reicht es für einen "Beweis"?

Input: Array arr with n integers 
Output: Array arr sorted upward 
repeat 
    swapped = false 
    for i = 1 to n-1 do 
     if arr[i] > arr[i+1] then 
     temp = arr[i] 
     arr[i] = arr[i+1] 
     arr[i+1] = temp 
     swapped = true 
     end if 
    end for 
until not swapped 

Answer 1

Ja, es ist stabil. Wenn Sie es implementieren mit

if arr[i] >= arr[i+1] then 

dann werden Sie die Stabilität verlieren.

Auch ja, stabil bedeutet: wenn 2 Dinge mit gleichen Schlüsseln in der gleichen Reihenfolge in der Eingabe erscheinen, aber auch in der Ausgabe, die sortiert ist. Sie benötigen stabile Sortieralgorithmen, wenn Sie zuerst nach Schlüssel1 sortieren und dann nach Schlüssel2 sortieren