Устойчив ли следующий алгоритм?

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

Следующий алгоритм представляет собой хорошо известную сортировку пузырьком. Я бы сказал, что он стабилен, потому что я не вижу, чтобы 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

sorting algorithm proof
person itaminul    schedule 12.06.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

person Thomas    schedule 12.06.2016