CODEWITHSUNDEEP
algorithm
joshuacos2777
joshuacos2777

Reputation: 7

Selection Algorithm either is stable or not?

I have a question related to selection sort algorithm.

I have this list that each item has a name and an age.

(( Tom 20) ( Bob 10) (Pat 30) (Sue 10))

If we sort the list by age (increasing order) .we can get the either of the list below.

(( Bob 10) ( Sue 10) (Tom 20) (Pat 30)) OR (( Sue 10) ( Bob 10) (Tom 20) (Pat 30))

here is the method that given

public static void selectionSort(int [] arr)
{
    final int n=arr.length;
    int least,temp;

    for(int i=0; i<n; i++)
    {
        least=i;

        for(int j=i; j<n; j++)              
          if(arr[j]<=arr[least])
             least=j;


       temp=arr[i];
       arr[i]=arr[least];
       arr[least]=temp;
    }
}

The question is algorithm is stable or not? If it is stable,how to make it not stable ?

if it is not stable ,how to make it stable?

I found out this list is not stable. am I correct? if i am wrong, can someone explain to me? Thank you

Upvotes: 0

Views: 38

Answers (3)

Filkolev
Filkolev

Reputation: 460

@mikefaheysd was faster, so I won't repeat what he explained. I'll just add some explanations based on your code.

What you need to figure out is what's the behaviour of the method when the objects are equal. Currently, it is unstable, since you use this:

if(arr[j]<=arr[least])
  least=j;

Assume at some point Bob's index is least (since he came first in the input array). When Sue comes, her index will now be least because you use <= for comparison. Sue will be moved before Bob and their relative order will change.

Now, if you change the comparison to < you'll have a stable sort since two objects considered equal won't change relative positions.

Upvotes: 0

mikefaheysd
mikefaheysd

Reputation: 126

A stable sort is one which preserves the original order of the input set, where the comparison algorithm does not distinguish between two or more items.

In your example, this would mean Bob would always come before Sue since that is the original order of the input set.

The unstable algorithm exhibits undefined behaviour when two elements are equal, it is perfectly possible that the order is sometimes preserved.

Since the behavior is undefined, i.e you get different orders of bob and sue each time you run it, it would indeed be unstable.

Upvotes: 1

joshuacos2777
joshuacos2777

Reputation: 7

I am sorry the method header is public static void selectionSort(int [] arr) { int least,temp; final int n=arr.length;

the rest is above.

Upvotes: 0

Related Questions