fork(3) download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <cassert>
  5.  
  6. int main() {
  7. 	int input[] { 100, 21, 22, 99, 1, 927, -50, -24, -160 };
  8.  
  9. 	/**
  10. 	 * Sorts the array lexicographically.
  11. 	 * 
  12. 	 * The trick is that we have to compare digits left-to-right
  13. 	 * (considering typical Latin decimal notation) and that each of
  14. 	 * two numbers to compare may have a different number of digits.
  15. 	 * 
  16. 	 * This probably isn't very efficient, so I wouldn't do it on
  17. 	 * "millions" of numbers. But, it works...
  18. 	 */
  19. 	std::sort(
  20. 		std::begin(input),
  21. 		std::end(input),
  22. 		[](int lhs, int rhs) -> bool {
  23. 			// Returns true if lhs < rhs
  24. 			// Returns false otherwise
  25. 			const auto BASE = 10;
  26. 			const bool LHS_FIRST = true;
  27. 			const bool RHS_FIRST = false;
  28.  
  29.  
  30. 			// There's no point in doing anything at all
  31. 			// if both inputs are the same.
  32. 			if (lhs == rhs) {
  33. 				return LHS_FIRST;
  34. 			}
  35.  
  36. 			// Compensate for sign
  37. 			if (lhs < 0 && rhs < 0) {
  38. 				// When both are negative, sign on its own yields
  39. 				// no clear ordering between the two arguments.
  40. 				// 
  41. 				// Remove the sign and continue as for positive
  42. 				// numbers.
  43. 				lhs *= -1;
  44. 				rhs *= -1;
  45. 			}
  46. 			else if (lhs < 0) {
  47. 				// When the LHS is negative but the RHS is not,
  48. 				// consider the LHS "first" always as we wish to
  49. 				// prioritise the leading '-'.
  50. 				return LHS_FIRST;
  51. 			}
  52. 			else if (rhs < 0) {
  53. 				// When the LHS is negative but the RHS is not,
  54. 				// consider the RHS "first" always as we wish to
  55. 				// prioritise the leading '-'.
  56. 				return RHS_FIRST;
  57. 			}
  58.  
  59. 			// Counting the number of digits in both the LHS and RHS
  60. 			// arguments is *almost* trivial.
  61. 			const auto lhs_digits = (
  62. 				lhs == 0
  63. 				? 1
  64. 				: std::ceil(std::log(lhs+1)/std::log(BASE))
  65. 			);
  66.  
  67. 			const auto rhs_digits = (
  68. 				rhs == 0
  69. 				? 1
  70. 				: std::ceil(std::log(rhs+1)/std::log(BASE))
  71. 			);
  72.  
  73. 			// Now we loop through the positions, left-to-right,
  74. 			// calculating the digit at these positions for each
  75. 			// input, and comparing them numerically. The
  76. 			// lexicographic nature of the sorting comes from the
  77. 			// fact that we are doing this per-digit comparison
  78. 			// rather than considering the input value as a whole.
  79. 			const auto max_pos = std::max(lhs_digits, rhs_digits);
  80. 			for (auto pos = 0; pos < max_pos; pos++) {
  81. 				if (lhs_digits - pos == 0) {
  82. 					// Ran out of digits on the LHS
  83. 					return LHS_FIRST;
  84. 				}
  85. 				else if (rhs_digits - pos == 0) {
  86. 					// ran out of digits on the RHS
  87. 					return RHS_FIRST;
  88. 				}
  89. 				else {
  90. 					const auto lhs_x = (lhs / static_cast<decltype(BASE)>(std::pow(BASE, lhs_digits - 1 - pos))) % BASE;
  91. 					const auto rhs_x = (rhs / static_cast<decltype(BASE)>(std::pow(BASE, rhs_digits - 1 - pos))) % BASE;
  92.  
  93. 					if (lhs_x < rhs_x)
  94. 						return LHS_FIRST;
  95. 					else if (rhs_x < lhs_x)
  96. 						return RHS_FIRST;
  97. 				}
  98. 			}
  99.  
  100. 			// If we reached the end and everything still
  101. 			// matches up, then something probably went wrong
  102. 			// as I'd have expected to catch this in the tests
  103. 			// for equality.
  104. 			assert("Unknown case encountered");
  105. 		}
  106. 	);
  107.  
  108. 	std::cout << '{';
  109. 	for (auto x : input)
  110. 		std::cout << x << ", ";
  111. 	std::cout << '}';
  112. }
Success #stdin #stdout 0s 3304KB
comments (?)
stdin 
Standard input is empty
stdout 
{-160, -24, -50, 1, 100, 21, 22, 927, 99, }
https://ideone.com/KbtvwM
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

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!