fork(4) download
copy 
  1. #include <iostream>
  2.  
  3. struct HighestNumber
  4. {
  5. 	int number;
  6. 	int index;
  7. };
  8.  
  9. void swap(int* array, int i, int j)
  10. {
  11. 	int temp = array[i];
  12. 	array[i] = array[j];
  13. 	array[j] = temp;
  14. }
  15.  
  16. HighestNumber getTheHighestNumber(int* array, int size)
  17. {
  18. 	int theHighest = 0;
  19. 	int index = 0;
  20. 	for (int i = 0; i != size; ++i)
  21. 	{
  22. 		if (i == 0)
  23. 			theHighest = array[0];
  24.  
  25. 		if (theHighest < array[i])
  26. 		{
  27. 			theHighest = array[i];
  28. 			index = i;
  29. 		}
  30.  
  31. 	}
  32.  
  33. 	return HighestNumber{ theHighest, index };
  34. }
  35.  
  36. void sortArray(int* array, int size)
  37. {
  38. 	do
  39. 	{
  40. 		for (int i = 0; i < size - 1; ++i)
  41. 		{
  42. 			if (array[i] > array[i + 1])
  43. 				swap(array, i, i + 1);
  44. 		}
  45. 		size--;
  46. 	} while (size > 1);
  47. }
  48.  
  49. int* algorithm(int* array, int size)
  50. {
  51. 	int* sortedArray = new int[size];
  52. 	int currentSortedArrayIndex = 0;
  53.  
  54. 	HighestNumber lastResult;
  55. 	HighestNumber bestResult = getTheHighestNumber(array, size);
  56.  
  57. 	do
  58. 	{
  59. 		lastResult = bestResult;
  60.  
  61. 		sortedArray[currentSortedArrayIndex] = bestResult.number;
  62. 		currentSortedArrayIndex++;
  63.  
  64. 		swap(array, bestResult.index, size - currentSortedArrayIndex);
  65.  
  66. 		bestResult = getTheHighestNumber(array, size - currentSortedArrayIndex);
  67.  
  68. 	} while (bestResult.number == lastResult.number);
  69.  
  70. 	sortArray(array, size - currentSortedArrayIndex);
  71.  
  72.  
  73. 	int toIterate = size - currentSortedArrayIndex;
  74. 	for (int i = 0; i != toIterate; ++i)
  75. 	{
  76. 		sortedArray[currentSortedArrayIndex] = array[i];
  77. 		currentSortedArrayIndex++;
  78. 	}
  79.  
  80. 	return sortedArray;
  81.  
  82.  
  83. }
  84.  
  85. int main()
  86. {
  87. 	int times = 0;
  88. 	std::cin >> times;
  89.  
  90. 	for (int i = 0; i != times; ++i)
  91. 	{
  92. 		int competitors = 0;
  93. 		std::cin >> competitors;
  94. 		int *array = new int[competitors];
  95. 		for (int j = 0; j != competitors; j++)
  96. 			std::cin >> array[j];
  97.  
  98. 		int *sortedArray = algorithm(array, competitors);
  99.  
  100. 		for (int j = 0; j != competitors; j++)
  101. 			std::cout << sortedArray[j] << " ";
  102.  
  103. 		std::cout << std::endl;
  104.  
  105. 		delete[] array;
  106. 		delete[] sortedArray;
  107. 	}
  108.  
  109. 	return 0;
  110. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
3
5
1 2 3 4 5
5
4 5 2 3 5
2
1 1
stdout
copy 
5 1 2 3 4 
5 5 2 3 4 
1 1
https://ideone.com/euvRo1
language:
C++14 (gcc 8.3)
created:
9 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!