Cách kiểm tra 1 algorithm sorting Stable hay unstable?

[Russia (Vũ Minh Thắng)]

Mình đc yêu cầu làm 1 class để check xem algorithm sorting có stable hay ko.
Ý tưởng ban đầu của mình là dùng pair nhưng ko thành công. Có ai có ý tưởng gì ko ạ? Xin cảm ơn.

[MeigyokuThmn (明玉)]

Thường thì với những bài kiểu này, mình hay giải quyết bằng hashmap, hoặc dùng cây nhị phân tìm kiếm như cây đỏ đen chẳng hạn (cứ như thể là map/hashmap can solve anything vậy), tất nhiên element bản thân chúng phải mang thông tin về vị trí gốc trước khi sắp xếp. Nhưng bạn thử nói xem “pair” của bạn là gì nào?

[hungaya (Hung)]

Pair?

[a,b,a,b]
[(a,0), (b,1), (a,2), (b,3)]

[(a,0), (a,2), (b,1), (b,3)] // stable
[(a,0), (a,2), (b,3), (b,1)] // unstable