Apr 16, 2014 at 12:25am UTC
How do you implement a code that tests if the sort (insertion, bubble, selection) is stable?
1. I have an array of ints (4, 5, 6, 5, 4, 6)
2. You assign each int with a particular ID.
Array (4, 5, 6, 5, 4, 6)
ID (1, 2, 3, 4, 5, 6)
The first element, which is four, is assigned with ID 1.
The second element, which is five, is assigned with ID 2.
and so on.......
3. Sort the array.
Array (4, 4, 5, 5, 6, 6)
ID (1, 5, 2, 4, 3, 6)
This sort is stable because
First int 4's ID (1) < second int 4's ID (5)
First int 5,s ID (2) < second int 5's ID (4)
Last edited on
Apr 16, 2014 at 12:32am UTC
Apr 16, 2014 at 1:03am UTC
Thank you for helping, but let's just say that they are randomly generated 1000 ints. How does that work in this case? because you would eventually run of alphabets to use as IDs.
Apr 16, 2014 at 7:56pm UTC
using std::multimap, place each value into the map along with it's corresponding ID. std::multimap allows the storage of multiple of the same value, and uses Red-black tree internally so the values are now sorted when inserted into the tree. Also the sorting is stable
Using your initial ID array, determine the number of times each value has to move to get into position if the sorting process is stable.
Sort your array using the sorting algorithm of your choice. And during the sorting process, update the ID array whenever a value moves
Last edited on
Apr 16, 2014 at 8:06pm UTC