Advertisement
Guest User

Untitled

a guest
Jan 18th, 2017
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.13 KB | None | 0 0
  1. class Main {
  2.  
  3. private static void linebreak() {
  4. System.out.println("------------------------------------------------------------");
  5. }
  6.  
  7. private static void printArray(int[] a) {
  8. for (int i = 0; i < a.length; i++) System.out.print(a[i] + " ");
  9. System.out.println("");
  10. }
  11.  
  12. // Time complexity of O(Logn)
  13. static int binarySearchRecursive(int[] arr, int l, int r,int x) {
  14. if(l<=r){
  15. int mid=(l+r)/2;
  16.  
  17. if(arr[mid]==x) return mid;
  18. if(arr[mid]<x) return binarySearchRecursive(arr,mid+1,r,x);
  19. else return binarySearchRecursive(arr,l,mid-1,x);
  20. }
  21. return -1;
  22. }
  23.  
  24. static int binarySearchIterative(int[] arr, int l, int r, int x) {
  25. if(l<=r) {
  26. int mid=(l+r)/2;
  27.  
  28. if(arr[mid]==x) return mid;
  29. if(arr[mid] < x) l = mid+1;
  30. else r = mid-1;
  31. }
  32. return -1;
  33. }
  34.  
  35. static void mergeSort(int[] arr, int l, int r) {
  36. if(l==r) return;
  37. else {
  38. int m = (l+r)/2;
  39. mergeSort(arr,l,m);
  40. mergeSort(arr,m+1,r);
  41. merge(arr,l,m,r);
  42. }
  43. }
  44.  
  45. static void merge(int[] arr,int l, int m, int r) {
  46. int i,j,k;
  47. int n1=m-l+1;
  48. int n2=r-m;
  49.  
  50. // Create temp arrays
  51. int[] L = new int[n1];
  52. int[] R = new int[n2];
  53.  
  54. // Copy data to temp arrays
  55. for(i=0;i<n1;i++) L[i]=arr[l+i];
  56. for(j=0;j<n2;j++) R[j]=arr[m+1+j];
  57.  
  58. // merge temp arrays back to arr[l..r]
  59. i=0;
  60. j=0;
  61. k=l;
  62.  
  63. while(i<n1 && j<n2) {
  64. if(L[i] <= R[j]) arr[k++] = L[i++];
  65. else arr[k++] = R[j++];
  66. }
  67. while(i<n1) arr[k++] = L[i++]; // Copy remaining elements of L[i]
  68. while(j<n2) arr[k++] = R[j++]; // Copy remaining elements of R[j]
  69. }
  70.  
  71.  
  72. // Insertion sort O(n*2)
  73. static int[] insertionSort(int[] list) {
  74. int i,j,key,temp;
  75. for(i=1;i<list.length;i++) {
  76. j=i-1;
  77. key = list[i];
  78.  
  79. while(j>=0 && list[j] > key) {
  80. // swap the elements
  81. temp = list[j];
  82. list[j] = list[j+1];
  83. list[j+1] = temp;
  84. j--;
  85. }
  86. }
  87. return list;
  88. }
  89.  
  90. // Selection sort O(n*2)
  91. static int[] selectionSort (int[] list) {
  92. int i, j, minValue, minIndex, temp = 0;
  93. for (i = 0; i < list.length; i++) {
  94. minValue = list[i];
  95. minIndex = i;
  96. for (j = i; j < list.length; j++) {
  97. if (list[j] < minValue) {
  98. minValue = list[j];
  99. minIndex = j;
  100. }
  101. }
  102. if (minValue < list[i]) {
  103. temp = list[i];
  104. list[i] = list[minIndex];
  105. list[minIndex] = temp;
  106. }
  107. }
  108. return list;
  109. }
  110.  
  111. // Bubble sort O(n*2)
  112. static int[] bubbleSort (int[] list) {
  113. int i, j, temp = 0;
  114. for (i = 0; i < list.length - 1; i++) {
  115. for (j = 0; j < list.length - 1 - i; j++) {
  116. if (list[j] > list[j + 1]) {
  117. temp = list[j];
  118. list[j] = list[j + 1];
  119. list[j + 1] = temp;
  120. }
  121. }
  122. }
  123. return list;
  124. }
  125.  
  126. public static void main(String[] args) {
  127.  
  128. int[] arr = {2,3,4,10,40};
  129. int result1 = binarySearchRecursive(arr,0,arr.length-1,10);
  130. if(result1 == -1) System.out.println("Element not present in the array");
  131. else System.out.println("Element present at index: " + result1);
  132. linebreak();
  133. int result2 = binarySearchRecursive(arr,0,arr.length-1,20);
  134. if(result2 == -1) System.out.println("Element not present in the array");
  135. else System.out.println("Element present at index: " + result2);
  136. linebreak();
  137. int[] arr2 = {4,6,3,8,10,9,7,2,1};
  138. System.out.println("Array before sorting:");
  139. printArray(arr2);
  140. mergeSort(arr2,0, arr2.length-1);
  141. System.out.println("Array after sorting:");
  142. printArray(arr2);
  143. linebreak();
  144. int[] arr3 = {4,6,3,8,10,9,7,2,1};
  145. System.out.println("Array before sorting:");
  146. printArray(arr3);
  147. insertionSort(arr3);
  148. System.out.println("Array after sorting:");
  149. printArray(arr3);
  150. linebreak();
  151. int[] arr4 = {4,6,3,8,10,9,7,2,1};
  152. System.out.println("Array before sorting:");
  153. printArray(arr4);
  154. selectionSort(arr4);
  155. System.out.println("Array after sorting:");
  156. printArray(arr4);
  157. linebreak();
  158. int[] arr5 = {4,6,3,8,10,9,7,2,1};
  159. System.out.println("Array before sorting:");
  160. printArray(arr5);
  161. bubbleSort(arr5);
  162. System.out.println("Array after sorting:");
  163. printArray(arr5);
  164. linebreak();
  165. }
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement