Является ли следующий алгоритм стабильным?

Question

Этот алгоритм стабилен или нет? Я проверил значение stable и нашел что-то на этом сайте. Если я правильно понял, что-то (мы говорим о алгоритмах сортировки) является стабильным, когда 2 вещи с одними и теми же клавишами отображаются в том же порядке на входе, но также и на сортировке, которая сортируется.

Следующий алгоритм - это известный Bubblesort. Я бы сказал, что он стабилен, потому что я не вижу, чтобы 2 равных элемента когда-либо менялись туда, поэтому он должен быть стабильным алгоритмом. Я прав, и этого достаточно для «доказательства»?

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

Да, стабильно. Если вы реализуете его

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

, то вы будете терять стабильность.

Также да, стабильный означает: когда 2 вещи с одинаковыми клавишами отображаются в том же порядке на входе, но также и на сортированном выходе. Вам нужны стабильные алгоритмы сортировки, когда вы сначала сортируете по key1, а затем сортируете по ключу2