Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Main {
- private static void linebreak() {
- System.out.println("------------------------------------------------------------");
- }
- private static void printArray(int[] a) {
- for (int i = 0; i < a.length; i++) System.out.print(a[i] + " ");
- System.out.println("");
- }
- // Time complexity of O(Logn)
- static int binarySearchRecursive(int[] arr, int l, int r,int x) {
- if(l<=r){
- int mid=(l+r)/2;
- if(arr[mid]==x) return mid;
- if(arr[mid]<x) return binarySearchRecursive(arr,mid+1,r,x);
- else return binarySearchRecursive(arr,l,mid-1,x);
- }
- return -1;
- }
- static int binarySearchIterative(int[] arr, int l, int r, int x) {
- if(l<=r) {
- int mid=(l+r)/2;
- if(arr[mid]==x) return mid;
- if(arr[mid] < x) l = mid+1;
- else r = mid-1;
- }
- return -1;
- }
- static void mergeSort(int[] arr, int l, int r) {
- if(l==r) return;
- else {
- int m = (l+r)/2;
- mergeSort(arr,l,m);
- mergeSort(arr,m+1,r);
- merge(arr,l,m,r);
- }
- }
- static void merge(int[] arr,int l, int m, int r) {
- int i,j,k;
- int n1=m-l+1;
- int n2=r-m;
- // Create temp arrays
- int[] L = new int[n1];
- int[] R = new int[n2];
- // Copy data to temp arrays
- for(i=0;i<n1;i++) L[i]=arr[l+i];
- for(j=0;j<n2;j++) R[j]=arr[m+1+j];
- // merge temp arrays back to arr[l..r]
- i=0;
- j=0;
- k=l;
- while(i<n1 && j<n2) {
- if(L[i] <= R[j]) arr[k++] = L[i++];
- else arr[k++] = R[j++];
- }
- while(i<n1) arr[k++] = L[i++]; // Copy remaining elements of L[i]
- while(j<n2) arr[k++] = R[j++]; // Copy remaining elements of R[j]
- }
- // Insertion sort O(n*2)
- static int[] insertionSort(int[] list) {
- int i,j,key,temp;
- for(i=1;i<list.length;i++) {
- j=i-1;
- key = list[i];
- while(j>=0 && list[j] > key) {
- // swap the elements
- temp = list[j];
- list[j] = list[j+1];
- list[j+1] = temp;
- j--;
- }
- }
- return list;
- }
- // Selection sort O(n*2)
- static int[] selectionSort (int[] list) {
- int i, j, minValue, minIndex, temp = 0;
- for (i = 0; i < list.length; i++) {
- minValue = list[i];
- minIndex = i;
- for (j = i; j < list.length; j++) {
- if (list[j] < minValue) {
- minValue = list[j];
- minIndex = j;
- }
- }
- if (minValue < list[i]) {
- temp = list[i];
- list[i] = list[minIndex];
- list[minIndex] = temp;
- }
- }
- return list;
- }
- // Bubble sort O(n*2)
- static int[] bubbleSort (int[] list) {
- int i, j, temp = 0;
- for (i = 0; i < list.length - 1; i++) {
- for (j = 0; j < list.length - 1 - i; j++) {
- if (list[j] > list[j + 1]) {
- temp = list[j];
- list[j] = list[j + 1];
- list[j + 1] = temp;
- }
- }
- }
- return list;
- }
- public static void main(String[] args) {
- int[] arr = {2,3,4,10,40};
- int result1 = binarySearchRecursive(arr,0,arr.length-1,10);
- if(result1 == -1) System.out.println("Element not present in the array");
- else System.out.println("Element present at index: " + result1);
- linebreak();
- int result2 = binarySearchRecursive(arr,0,arr.length-1,20);
- if(result2 == -1) System.out.println("Element not present in the array");
- else System.out.println("Element present at index: " + result2);
- linebreak();
- int[] arr2 = {4,6,3,8,10,9,7,2,1};
- System.out.println("Array before sorting:");
- printArray(arr2);
- mergeSort(arr2,0, arr2.length-1);
- System.out.println("Array after sorting:");
- printArray(arr2);
- linebreak();
- int[] arr3 = {4,6,3,8,10,9,7,2,1};
- System.out.println("Array before sorting:");
- printArray(arr3);
- insertionSort(arr3);
- System.out.println("Array after sorting:");
- printArray(arr3);
- linebreak();
- int[] arr4 = {4,6,3,8,10,9,7,2,1};
- System.out.println("Array before sorting:");
- printArray(arr4);
- selectionSort(arr4);
- System.out.println("Array after sorting:");
- printArray(arr4);
- linebreak();
- int[] arr5 = {4,6,3,8,10,9,7,2,1};
- System.out.println("Array before sorting:");
- printArray(arr5);
- bubbleSort(arr5);
- System.out.println("Array after sorting:");
- printArray(arr5);
- linebreak();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement