fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <ctime>
  5.  
  6. struct Data
  7. {
  8.    int key;
  9.    int original_index;
  10. };
  11.  
  12. bool compare_with_itself_called = false;
  13. bool pointer_order_changed = false;
  14.  
  15. int compare(const void *p1, const void *p2)
  16. {
  17.    if(p1==p2)
  18.    {
  19.    	  compare_with_itself_called = true;
  20.    	  return 0;
  21.    }
  22.    const Data *d1 = (const Data*)p1;
  23.    const Data *d2 = (const Data*)p2;
  24.    if(d1->key < d2->key)
  25.      return -1;
  26.    if(d2->key < d1->key)
  27.      return 1;
  28.    bool index_cond = d1->original_index<d2->original_index;
  29.    bool ptr_cond = (p1<p2);
  30.    if(index_cond!=ptr_cond)
  31.    {
  32.    	  pointer_order_changed = true;
  33.    }
  34.    return index_cond ? -1 : 1;
  35. }
  36.  
  37. void outputArray(Data d[], unsigned n)
  38. {
  39. 	for(unsigned i=0; i!=n; ++i)
  40. 	   std::cout << d[i].key << "@" << d[i].original_index << std::endl;
  41. }
  42.  
  43. bool isStableSorted(const std::vector<Data>& d)
  44. {
  45.    size_t n = d.size();
  46.    for(size_t i=1; i<n; ++i)
  47.    {
  48.       if(d[i-1].key==d[i].key &&
  49.          d[i-1].original_index>d[i].original_index)
  50.          return false;
  51.    }
  52.    return true;
  53. }
  54.  
  55. int main()
  56. {
  57.    srand((unsigned)time(0));
  58.    const unsigned NPASSES = 100000;
  59.    unsigned nStableSorted = 0;
  60.    for(unsigned pass=0; pass<NPASSES; ++pass)
  61.    {
  62.       unsigned N = rand()*1000/RAND_MAX+1;
  63.       unsigned K = N/5+1;
  64.       unsigned M = rand()*K/RAND_MAX+1;
  65.       //
  66.       std::vector<Data> d(N);
  67.       for(unsigned i=0; i<N; ++i)
  68.       {
  69.          d[i].key = rand()*M/RAND_MAX+1;
  70.          d[i].original_index = i;
  71.       }
  72.       //
  73.       qsort(&(d[0]), N, sizeof(Data), compare);
  74.       //
  75.       if(isStableSorted(d))
  76.          ++nStableSorted;
  77.    }
  78.    std::cout << "Total arrays sorted: " << NPASSES << std::endl;
  79.    std::cout << "Stable-sorted arrays: " << nStableSorted << std::endl;
  80.    std::cout << "compare_with_itself_called="
  81.       << (compare_with_itself_called ? "true" : "false") << std::endl;
  82.    std::cout << "pointer_order_changed="
  83.       << (pointer_order_changed ? "true" : "false") << std::endl;
  84.    return 0;
  85. }
  86.  
  87.  
Success #stdin #stdout 0.02s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Total arrays sorted: 100000
Stable-sorted arrays: 100000
compare_with_itself_called=false
pointer_order_changed=false
https://ideone.com/KOYbgJ
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!