CODEWITHSUNDEEP
algorithmsortingproof
itaminul
itaminul

Reputation: 53

Is the following algorithm stable?

This algorithm is stable or not? I have checked the meaning of stable and found something on this site. If I understood correctly, something (we talk about sort algorithms) is stable when 2 things with same keys appear in same order in the input but also in the output which is sorted.

The following algorithm is the well known Bubblesort. I would say it is stable because I cannot see that 2 equal elements ever get swapped there, thus it must be stable algorithm. Am I right and is it enough for a "proof"?

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

Upvotes: 1

Views: 68

Answers (1)

Thomas
Thomas

Reputation: 2259

yes, it is stable. If you implement it with

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

then you'll loose the stability.

Also yes, stable means: when 2 things with same keys appear in same order in the input but also in the output which is sorted. You need stable sort algorithms, when you first sort by key1 and then sort by key2

Upvotes: 1

Related Questions