### Sorting Algorithm

How do you implement a code that tests if the sort (insertion, bubble, selection) is stable?

For example,

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)

Thank you

Last edited on
Something like this:

 ``123456789101112131415161718192021`` ``````#include #include #include #include int main() { using pair = std::pair ; pair a[] = { { 6, 'a' }, { 5, 'b' }, { 4, 'c' }, { 5, 'd' }, { 4, 'e' }, { 6, 'f' }, { 5, 'g'}, { 4, 'h' } } ; // int-value, char-id for( auto p : a ) std::cout << '{' << p.first << ',' << p.second << "} " ; std::cout << '\n' ; const auto cmp = [] ( pair a, pair b ) { return a.first < b.first ; } ; std::stable_sort( std::begin(a), std::end(a), cmp ) ; for( auto p : a ) std::cout << '{' << p.first << ',' << p.second << "} " ; std::cout << '\n' ; }``````

 ```{6,a} {5,b} {4,c} {5,d} {4,e} {6,f} {5,g} {4,h} {4,c} {4,e} {4,h} {5,b} {5,d} {5,g} {6,a} {6,f}```

http://coliru.stacked-crooked.com/a/da101955999c21f0
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.
> because you would eventually run of alphabets to use as IDs.

The id does not have to be a `char`; for instance it can be an integer.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243`` ``````#include #include #include #include #include #include #include #include int main() { using pair = std::pair< int, std::size_t > ; // int-value, std::size_t id constexpr std::size_t N = 1000000 ; constexpr int MIN = 4 ; constexpr int MAX = 10 ; std::vector seq(N) ; { std::mt19937 rng( std::time(nullptr) ) ; std::uniform_int_distribution distr( MIN, MAX ) ; // monotonically increasing ids for( std::size_t i = 0 ; i < N ; ++i ) seq[i] = { distr(rng), i } ; } const auto cmp_val = [] ( pair a, pair b ) { return a.first < b.first ; } ; std::stable_sort( std::begin(seq), std::end(seq), cmp_val ) ; assert( std::is_sorted( std::begin(seq), std::end(seq) ) ) ; // to test the stability of the sort, lexicographical comparison // of the pairs is adequate as the original ids were monotonically increasing // eqivalent to: for( int value = MIN ; value <= MAX ; ++value ) { const auto eq_val = [value] ( pair p ) { return p.first == value ; } ; auto begin = std::find_if( seq.begin(), seq.end(), eq_val ) ; auto end = std::find_if( seq.rbegin(), seq.rend(), eq_val ).base() ; const auto cmp_id = [] ( pair a, pair b ) { return a.second < b.second ; } ; assert( std::is_sorted( begin, end, cmp_id ) ) ; } }``````

http://coliru.stacked-crooked.com/a/fb1999ca023af1a9
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
Example: http://coliru.stacked-crooked.com/a/226935d5217f522b

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.
Example: http://coliru.stacked-crooked.com/a/394e3f4479e3df82

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
Topic archived. No new replies allowed.