Sorting Algorithm

[jshm415]

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

[JLBorges]

Something like this:

#include <iostream>
#include <algorithm>
#include <utility>
#include <iterator>

int main()
{
    using pair = std::pair<int,char> ;

    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

[jshm415]

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.

[JLBorges]

> 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.

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <iterator>
#include <random>
#include <ctime>
#include <cassert>

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<pair> seq(N) ;

    {
        std::mt19937 rng( std::time(nullptr) ) ;
        std::uniform_int_distribution<int> 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

[Smac89]

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