CODEWITHSUNDEEP
algorithmsorting
Sahil
Sahil

Reputation: 9480

Can selection be made stable?

Hi I am working on the code stable selection sort,and I have been able to get the correct result, but I am not sure if there are corner cases in the code.The data I am sorting like this
a[0]=new Data(1,'d');
a[1]=new Data(2,'c');
a[2]=new Data(3,'a');
a[3]=new Data(4,'b');
a[4]=new Data(5,'d');
a[5]=new Data(6,'c');
a[6]=new Data(8,'a');
a[7]=new Data(9,'a');
a[8]=new Data(10,'a');

as you can see it is sorted by numbers and I am supposed to sort it by characters now.

So the logic of sort of Data objects I have used is like this:

in the loop of finding the smallest element, we will not just find the smallest element but smallest element with smallest int. That way order of the elements will remain the same

even though it is working just fine, are there any corner cases I have missed here?

for ex : lets take up itunes, first we sort by the ids of the songs and after that we want to sort by their names. I hope it makes every thing clear

Upvotes: 1

Views: 156

Answers (2)

ltjax
ltjax

Reputation: 15997

No, you have not missed anything. This is the standard technique to make any unstable algorithms stable: impose a total ordering! Any ties are resolved by the second key - which is the input order. I assume you correctly implemented lexicographical ordering here, it's not entirely clear from your description.

Upvotes: 1

mcdowella
mcdowella

Reputation: 19601

What you have described is a sort on a composite key: the most significant part of the key is the character, and the least significant part of the key is the number.

This is not what I would call a stable sort. With a stable sort, where two records have the same value of the key, the first one in the sorted sequence is the first one in the original data, but in your case the first one is the one with the lowest number.

With a stable sort, if you gave it data in which the numbers were in descending order, then if two records had the same letter, the first record of the two in the sorted data would be the record with the largest number, because this is the first record in the input data. With your program, the first record of the two would be the record with the smallest number.

Upvotes: 0

Related Questions