fork download
copy 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <deque>
  4. #include <ctime>
  5.  
  6. using namespace std;
  7.  
  8. void ReadArray( deque<int> & arr )
  9. {
  10. 	ifstream arrfile("IntegerArray.txt");
  11. 	int a;
  12. 	while( arrfile >> a )
  13. 	{
  14. 		arr.push_back( a );
  15. 	}
  16. }
  17. unsigned long MergeSortInversions(
  18. 	const deque<int> & in,
  19. 	int from, int to,
  20. 	deque<int> & out
  21. 	)
  22. {
  23. 	int diff = to - from;
  24. 	if( diff == 0 )
  25. 	{
  26. 		out.push_back( in[from] );
  27. 		return 0;
  28. 	}
  29.  
  30. 	int div = (from + to) / 2;
  31. 	deque<int> aleft;
  32. 	unsigned long inv_left = MergeSortInversions( in, from, div, aleft );
  33. 	deque<int> aright;
  34. 	unsigned long inv_right = MergeSortInversions( in, div+1, to, aright );
  35. 	unsigned long invs = 0;
  36. 	while( aleft.size() != 0 && aright.size() != 0 )
  37. 	{
  38. 		int lval = *aleft.begin();
  39. 		int rval = *aright.begin();
  40. 		if( lval < rval )
  41. 		{
  42. 			out.push_back( lval );
  43. 			aleft.pop_front();
  44. 		}
  45. 		else
  46. 		{
  47. 			out.push_back( rval );
  48. 			aright.pop_front();
  49. 			invs += aleft.size();
  50. 		}
  51. 	}
  52. 	out.insert( out.end(), aright.begin(), aright.end() );
  53. 	out.insert( out.end(), aleft.begin(), aleft.end() );
  54. 	return inv_left + inv_right + invs;
  55. }
  56.  
  57. unsigned long MergeSortInversions( const deque<int> & arr )
  58. {
  59. 	deque<int> sorted;	
  60. 	unsigned long int invs = MergeSortInversions( arr, 0, arr.size()-1, sorted);
  61. 	return invs;
  62. }
  63.  
  64. int main( /*int argc, char * argv[]*/ )
  65. {
  66. 	deque<int> arr;
  67. 	ReadArray( arr );
  68. 	unsigned long int good_result = 2407905288U;
  69. 	cout <<  "Expected result: " << good_result << endl;
  70. 	cout << "Array of " << arr.size() << " elements." << endl;
  71. 	clock_t t = clock();
  72. 	unsigned long int merge_inv = MergeSortInversions( arr );
  73. 	t = clock() - t;
  74. 	cout << "Merge inv: " << merge_inv << endl;
  75. 	float ft = ((float)t)/CLOCKS_PER_SEC;
  76. 	cout << "Completed in " << t << " : " << ft << endl;
  77. 	return 0;
  78. }
  79.  
Runtime error #stdin #stdout 0.02s 29368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Expected result: 2407905288
Array of 0 elements.
https://ideone.com/67OSJX
language:
C++ (gcc 8.3)
created:
11 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!