Advertisement
wurdalak007

Untitled

Oct 25th, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. //void Merch( vector<int> &first, vector<int> &second){
  9. // int i = 0;
  10. // int j = 0;
  11. // vector<int> SortArr( first.size() + second.size() );
  12. //
  13. // while( i < first.size() && j < second.size() ) {
  14. // if( first[i] > second[j] ) {
  15. // SortArr[i+j] = second[j];
  16. // j++;
  17. // } else {
  18. // SortArr[i+j] = first[i];
  19. // i++;
  20. // }
  21. // }
  22. //
  23. // if( i == first.size() ) {
  24. // for( ; j < second.size(); j++ ) {
  25. // SortArr[i+j] = second[j];
  26. // }
  27. // } else {
  28. // for( ; i < first.size(); i++ ) {
  29. // SortArr[i+j] = first[i];
  30. // }
  31. // }
  32. //}
  33.  
  34. void SiftDown( vector<int> &arr, int i, int last ){
  35. int j = 0;
  36. int left = 0;
  37. int right = 0;
  38.  
  39. while( i < last ) {
  40. j = i;
  41. left = (2 * i) + 1;
  42. right = left + 1;
  43.  
  44. if( left < last && arr[j] < arr[left] ) {
  45. j = left;
  46. }
  47.  
  48. if( right < last && arr[j] < arr[right] ) {
  49. j = right;
  50. }
  51.  
  52. if( j == i ) return ;
  53. swap( arr[j], arr[i] );
  54. i = j;
  55. }
  56. }
  57.  
  58. void BuildHeap( vector<int> &arr, int right ) {
  59. for( int i = right/2 - 1 ; i >= 0; i-- ) {
  60. SiftDown( arr, i, right );
  61. }
  62. }
  63.  
  64. void HeapSort( vector<int> &arr, int right ){
  65. int last = right;
  66. BuildHeap( arr, right );
  67.  
  68. while( last > 0 ) {
  69. swap( arr[0], arr[last] );
  70. SiftDown( arr, 0, last );
  71. last--;
  72. }
  73. }
  74.  
  75. int med (vector<int> &arr, int right, int left)
  76. {
  77. int middle = (right+left)/2;
  78. if (arr[right] > arr[middle]) {
  79. if (arr[left] > arr[right]){
  80. return right;
  81. }
  82. return (arr[middle] > arr[left]) ? middle : left;
  83. }
  84. if (arr[left] > arr[middle]){
  85. return middle;
  86. }
  87. return (arr[right] > arr[left]) ? right : left;
  88. }
  89.  
  90. void InsertionSort( vector<int> &arr, int left, int right ){
  91. for( int i = left + 1; i < right; ++i ) {
  92. int tmp = arr[i];
  93. int j = i - 1;
  94. for( ; j >= left && tmp < arr[j]; --j ) {
  95. arr[j + 1] = arr[j];
  96. }
  97. arr[j + 1] = tmp;
  98. }
  99. }
  100.  
  101. int Partition ( vector<int> &arr, int left, int right) {
  102. int i = left;
  103. int j = right - 1;
  104. int median = med(arr, right, left);
  105. int pivot = arr[median];
  106.  
  107. while ( i <= j ) {
  108. for ( ; i <= right && ( arr[i] < pivot ); i++ ) {
  109. }
  110. for ( ; j >= left && ( arr[j] >= pivot ); j-- ) {
  111. }
  112. if ( i < j ) {
  113. swap ( arr[i++], arr[j--] );
  114. }
  115. }
  116. swap ( arr[i], arr[median] );
  117.  
  118. return i;
  119. }
  120.  
  121. void QSort ( vector<int> &arr, int left, int right ) {
  122. if ( right - left >= 11 ) {
  123. int part = Partition(arr, left, right);
  124. QSort(arr, left, part - 1);
  125. QSort ( arr, part + 1, right );
  126. } else {
  127. InsertionSort(arr, left, right + 1);
  128. }
  129. }
  130.  
  131. int main() {
  132. int n = 0;
  133. int tmp = 0;
  134. vector<int> arr(0);
  135. ifstream text("input.txt");
  136.  
  137. while (!text.eof()){
  138. text >> tmp;
  139. arr.push_back(tmp);
  140. }
  141. arr.pop_back();
  142.  
  143. text.close();
  144. n = arr.size();
  145. QSort ( arr, 0, n - 1 );
  146. for ( int i = 9; i < n; i=i+10 ) {
  147. printf("%d", arr[i]);
  148.  
  149. }
  150.  
  151. return 0;
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement