Advertisement
djemm1996

Untitled

Feb 25th, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.54 KB | None | 0 0
  1. import java.util.Random;
  2. import java.util.Scanner;
  3. public class Ld_test {
  4.  
  5. public static void firstMethod(int[] a) { //1.metode - uzlabota ieklausanas metode
  6.  
  7. long t1 = System.nanoTime();
  8. int b[] = new int[2 * a.length - 1];
  9. int l = a.length - 1;
  10. int r = l;
  11. b[r] = a[0];
  12.  
  13.  
  14. for (int i = 1; i < a.length; i++) {
  15. if (b[l] >= a[i]) {
  16. l--;
  17. b[l] = a[i];
  18.  
  19. } else if
  20. (b[r] <= a[i]) {
  21. r++;
  22. b[r] = a[i];
  23. }
  24. else
  25. {
  26. int j;
  27. for (j = l; j <= r; j++) {
  28.  
  29.  
  30. if (a[i] <= b[j])
  31. break;
  32. }
  33. if (j - l < r - j) {
  34. for (int k = l; k <= j - 1; k++)
  35. b[k - 1] =b[k];
  36. l--;
  37. b[j - 1] = a[i];
  38. }
  39. else
  40. {
  41. for (int k = r; k >= j; k--)
  42. b[k + 1] = b[k];
  43. r++;
  44. b[j] = a[i];
  45. }
  46. }
  47. }
  48. for (int i = 0; i < a.length; i++) {
  49. a[i] = b[l];
  50. l++;
  51.  
  52. }
  53. long t2 = System.nanoTime();
  54. long t = t2 - t1;
  55. System.out.println("t="+t);
  56. }
  57.  
  58.  
  59. public static void secondMethod(int[] a) { //2.metode - Hoara bez rekursijas
  60.  
  61. long startTime = System.nanoTime();
  62. int left[] = new int[a.length / 2];
  63. int right[] = new int[a.length / 2];
  64.  
  65. short p = 0;
  66.  
  67. int stackpos = 1;
  68. int m = 0, l = 0, r = 0 ,i = 0, j = 0;
  69.  
  70. left[0] = 0;
  71. right[0] = a.length - 1;
  72. p = 3;
  73. do {
  74. switch (p) {
  75.  
  76. case 3:
  77. stackpos -= 1;
  78. l = left[stackpos];
  79. r = right[stackpos];
  80. p = 4;
  81. break;
  82.  
  83. case 4:
  84. m = (a[l] + a[r]) / 2;
  85. i = l;
  86. j = r;
  87. p = 6;
  88. break;
  89.  
  90. case 6:
  91.  
  92. while (a[i] < m) i++;
  93. while (a[j] > m) j--;
  94. if (i <= j) {
  95. int temp = a[i];
  96. a[i] = a[j];
  97. a[j] = temp;
  98. i++;
  99. j--;
  100. }
  101.  
  102. if (i <= j) {
  103. p = 6;
  104. break;
  105. }
  106.  
  107. if (i < r) {
  108. left[stackpos] = i;
  109. right[stackpos] = r;
  110. stackpos += 1;
  111. }
  112. r = j;
  113. if (l < r) {
  114. p = 4;
  115. break;
  116. }
  117. if (stackpos > 0) {
  118. p = 3;
  119. break;
  120. } else p = 1;
  121. break;
  122. }
  123. } while (p != 1);
  124. long estimatedTime = System.nanoTime() - startTime;
  125. System.out.println("t=" + estimatedTime);
  126. return;
  127. }
  128.  
  129. public static void main(String[] args) { //3.daļa - masīva izvade
  130. int numurs;
  131. int metode;
  132.  
  133. System.out.println("Anete Brenčuka RDBF0 161RDB155");
  134. System.out.print("method: ");
  135.  
  136. Scanner sc = new Scanner(System.in);
  137. if (sc.hasNextInt()){
  138. numurs = sc.nextInt();
  139. }
  140. else
  141. {
  142. System.out.println("input-output error");
  143. sc.close();
  144. return;
  145. }
  146.  
  147. if (numurs != 1 && numurs != 2) {
  148. System.out.println("input-output error");
  149. sc.close();
  150. return;
  151. }
  152. System.out.print("count: ");
  153.  
  154. if (sc.hasNextInt())
  155. metode = sc.nextInt();
  156.  
  157. else {
  158. System.out.println("input-output error");
  159. sc.close();
  160. return;
  161. }
  162.  
  163. int a[] = new int[metode];
  164. Random randomNumberGenerator = new Random();
  165. for (int i = 0; i < a.length; i++) {
  166. a[i] = randomNumberGenerator.nextInt();
  167. }
  168. sc.close();
  169.  
  170. switch (numurs) {
  171. case 1: firstMethod(a);
  172. break;
  173. case 2: secondMethod(a);
  174. break;
  175. default:
  176. System.out.println("input-output error");
  177. return;
  178. }
  179. System.out.println("sorted: ");
  180.  
  181. for (int i = 0; i < a.length; i++)
  182. System.out.print(a[i] + " ");
  183. }
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement