fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. void DutchNationalFlag4(int * arr , int n )
  6. {
  7. 	int low = 0 , mid1 = 0 , mid2 = n- 1 , high = n-1 ;
  8. 	int temp;
  9.  
  10. 	// This type of problems are best solved by using invariants 
  11.  
  12. 	// arr[ 0 .. low -1 ] conatins 0
  13. 	// arr[ low .. mid1 -1 ] contains 1
  14. 	// arr[ mid1 .. mid2 ] is unknown
  15. 	// arr[ mid2 + 1 ... high - 1 ] contains 2
  16. 	// arr[ high .. n-1 ] contains 3
  17.  
  18. 	// termination condition : Evert Iteration unkown length decreases so eventually will be Zero
  19. 	while( mid1 <= mid2 )
  20. 	{
  21. 		switch( arr[ mid1 ])
  22. 		{
  23. 			case 0 :
  24. 			{
  25. 				std::swap( arr[ low ] , arr [ mid1 ] );
  26. 				low ++ ;
  27. 				mid1 ++;
  28. 				break;
  29. 			}
  30.  
  31. 			case 1 :
  32. 			{
  33. 				mid1 ++;
  34. 				break;
  35. 			}
  36.  
  37. 			case 2 :
  38. 			{
  39. 				std::swap( arr[ mid1 ] , arr[ mid2 ]);
  40. 				mid2 -- ;
  41. 				break;
  42. 			}
  43.  
  44. 			case 3 :
  45. 			{
  46. 				//std::swap( arr[ mid1 ] , arr[ mid2 ]);
  47. 				std::swap( arr[ mid1 ] , arr[ high ]);
  48. 				mid2 --;
  49. 				high --;
  50. 				break;
  51. 			}
  52.  
  53. 		}
  54. 	}
  55.  
  56. 	for( int i =0 ; i < n ; i++)
  57. 	{
  58. 		cout << arr[ i ] << " " ;
  59. 	}
  60. }
  61.  
  62. int main() {
  63. 	int arr[] = {1,2,3,0,2,1,3,0,2,1,0,1,3,1,0,2,1,0};
  64. 	int n = sizeof(arr) / sizeof(arr[0]) ;
  65. 	DutchNationalFlag4(arr , n );
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0 0 1 1 1 1 1 1 2 3 2 2 2 3 3
https://ideone.com/nqvifU
Dutch National Flag problem with 4 colors
language:
C++14 (gcc 8.3)
created:
3 days 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!