Advertisement
Guest User

Untitled

a guest
Nov 27th, 2014
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.47 KB | None | 0 0
  1. //============================================================================
  2. // Name : Algo7Module2.cpp
  3. // Author :
  4. // Version :
  5. // Copyright : Your copyright notice
  6. // Description : Hello World in C++, Ansi-style
  7. //============================================================================
  8.  
  9. #include <iostream>
  10. #include <assert.h>
  11. #include <cstdio>
  12. #include <stdlib.h>
  13.  
  14. using namespace std;
  15.  
  16. struct limit {
  17. int left;
  18. int right;
  19. limit(){
  20. left = 0;
  21. right = 0;
  22. }
  23. };
  24.  
  25. class CQueue{
  26. public:
  27. CQueue(int n){
  28. this->tail = 0;
  29. this->head = 0;
  30. this->array = new limit[n];
  31. this->array_length = n;
  32. }
  33. ~CQueue(){
  34. delete (this->array);
  35. }
  36. limit pop_f();
  37. void push_b(limit data);
  38. bool isEmpty();
  39. private:
  40. int tail;
  41. int head;
  42. limit *array;
  43. int array_length;
  44. void expand();
  45.  
  46. };
  47. limit CQueue::pop_f(){
  48. if (this->head != this->tail){
  49. limit result = this->array[this->head];
  50. this->array[this->head].left = 0;
  51. this->array[this->head].right = 0;
  52. this->head = ((this->head + 1) % this->array_length);
  53. return result;
  54. }
  55. };
  56. bool CQueue::isEmpty(){
  57. return this->tail == this->head;
  58. }
  59.  
  60. void CQueue::expand(){
  61. limit *new_array = new limit[this->array_length * 2];
  62.  
  63. int counter = 0;
  64. int i = this->head;
  65. while(counter != this->array_length){
  66. new_array[counter++] = this->array[i];
  67. i = ((i+1) % this->array_length);
  68. }
  69. this->tail = array_length;
  70. this->head = 0;
  71. this->array_length *= 2;
  72. delete[] this->array;
  73. this->array = new_array;
  74.  
  75. }
  76.  
  77. void CQueue::push_b(limit data){
  78. this->array[tail] = data;
  79. this->tail = ((this->tail + 1) % this->array_length);
  80. if ( this->tail == this->head ){
  81. expand();
  82. }
  83. };
  84.  
  85. void insertionSort(int* a, int left, int right) {
  86. if (right - left < 2){
  87. return;
  88. } else {
  89. for(int i = left+1; i <= right; i++ ) {
  90. for(int j = i-1; j >= left && a[j] > a[j+1];j--) {
  91. swap(a[j], a[j+1]);
  92. }
  93. }
  94. }
  95.  
  96. }
  97.  
  98. int partition(int* arr, int left, int right, int piv) {
  99. int pivotValue = arr[piv];
  100. swap(arr[piv],arr[right]);
  101. for (int i = left; i < right; i++){
  102. if (arr[i] < pivotValue){
  103. swap (arr[piv],arr[left]);
  104. left++;
  105. }
  106. }
  107. swap(arr[left],arr[right]);
  108. return left;
  109. }
  110.  
  111. void ModQuickSort(int* arr, int n) {
  112. CQueue range(100000);
  113. int left = 0;
  114. int right = n - 1;
  115. int piv = 0;
  116. bool flag = true;
  117. while (flag){
  118. while(true) {
  119. piv = left + rand() % (right - left);
  120. if( right - left < 11 ) {
  121. insertionSort(arr, left, right);
  122. break;
  123. }
  124. piv = partition(arr, left, right, piv);
  125. limit buf;
  126. buf.left = piv+1;
  127. buf.right= right;
  128. range.push_b(buf);
  129. right = piv;
  130. };
  131. while((right != n-1) && (right - left < 11)) {
  132. limit buf = range.pop_f();
  133. left = buf.left;
  134. right = buf.right;
  135. if( right - left < 11 ) {
  136. insertionSort(arr, left, right);
  137. }
  138. }
  139. if (range.isEmpty() || right-left < 11){
  140. flag = false;
  141. }
  142. } ;
  143. }
  144.  
  145. int main() {
  146.  
  147. int* arr = new int[25000000];
  148. int n = 0;
  149.  
  150. while(true) {
  151. if (scanf("%d", &arr[n]) == 1){
  152. n++;
  153. } else {
  154. break;
  155. }
  156. }
  157.  
  158. ModQuickSort(arr, n);
  159.  
  160. for( int i = 9; i < n; i += 10 ) {
  161. cout << arr[i];
  162. }
  163.  
  164. return 0;
  165. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement