MergeSort

MergeSort

package sort;

import java.util.Arrays;

/*MergeSort is DIVIDE AND CONQUER
 DIVIDE - divide the array recursively till it contains single element (1-->half-->quarter ...so on)
 CONQUER - merge the divided arrays in sorted order
 
 * */


/**
 * @author sachin4java@blogspot.com
 *
 */
public class MergeSort {

public static void main(String[] args) {
int arr[] = {64,25,12,22,11};
System.out.println("Given array"+Arrays.toString(arr));
       sort(arr,0,arr.length-1);
       System.out.println("Sorted array"+Arrays.toString(arr));

}

public static void sort(int[] arr, int start, int end){

if(start<end){
//find middle
int m = (start+end)/2;
//divide the array recursively
sort(arr,start,m);
sort(arr,m+1,end);

//merge the above divided arrays in sorted order

merge(arr, start,m,end);


}

}

private static void merge(int[] arr, int start, int m, int end) {
//first create left and right arrays
//sizes of arrays
int s1 = m-start+1;
int s2 = end-m;

int left[] = new int[s1];
int right[] = new int[s2];

//copy the elemnts of arrays
for (int i = 0; i < s1; ++i) {
left[i]=arr[start+i];
}
for (int i = 0; i < s2; ++i) {
right[i]=arr[m+1+i];
}

//now merge in sorted fashion
int i=0,j=0;//for start index of left and right arrays
int k=start;// this will keep the index position in main array
while(i<s1 && j<s2){

if(left[i]<=right[j]){
arr[k]=left[i];
i++;
}else {
arr[k]=right[j];
j++;

}
//increment index by 1
k++;

}
//also there are possibilities that array having some remaaining elements
//lets add it in maain array with index k
while(i<s1){
arr[k]=left[i];
i++;
k++;
}
while(j<s2){
arr[k]=right[j];
j++;;
k++;
}


}

}

OUTPUT:

Given array[64, 25, 12, 22, 11]

Sorted array[11, 12, 22, 25, 64]

SelectionSort

SelectionSort


package sort;

import java.util.Arrays;

/*The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
*/
/**
 * @author sachin4java@blogspot.com
 *
 */
public class SelectionSort {

public static void main(String[] args) {

       int arr[] = {64,25,12,22,11};
       sort(arr);
       System.out.println("Sorted array"+Arrays.toString(arr));

}

public static void sort(int[] arr){
for (int i = 0; i < arr.length; i++) {

int min_idx=i;
//this whole iteration will find one minimum element and will put into sorted position
for (int j = i+1; j < arr.length; j++) {
if(arr[j]<arr[min_idx]){
min_idx=j;
}
}
//swap the minimum element
int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;


}
}

}

OUTPUT:

Given array[64, 25, 12, 22, 11]

Sorted array[11, 12, 22, 25, 64]

InsertionSort.java

InsertionSort

package sort;

import java.util.Arrays;

/*Insertion sort is to take  insert index point(here we have taken 1) and then check this index element
with all elements from left side to find the insert position.

In each iteration, we get the fixed position of the element
*/
public class InsertionSort {

public static void main(String[] args) {

       int arr[] = {64,25,12,22,11};
       System.out.println("Given array"+Arrays.toString(arr));
       sort(arr);
       System.out.println("Sorted array"+Arrays.toString(arr));

}

public static void sort(int[] arr){

for (int i = 1; i < arr.length; i++) {
int index = arr[i];
int j=i-1;  //for going index right to left element position

while(j>=0 && arr[j]>index){
arr[j+1]=arr[j];//move element postion by one to make space for index element
j=j-1;
}

arr[j+1]=index; //add the index element at this position

}
}

}


OUTPUT:

Given array[64, 25, 12, 22, 11]
Sorted array[11, 12, 22, 25, 64]

BubbleSort.java

BubbleSort



package sort;

import java.util.Arrays;
/*bubble sort swap adjacent elements in order from left to right, So in each
iteration, we get sorted array at right most part.
We need to handle this with skippign rightmost sorted part.

Just remember : second for loop (j<arr.length-i-1) which skips sorted part

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
*/
/**
 * @author sachin4java@blogspot.com
 *
 */
public class BubbleSort {

public static void main(String[] args) {
int arr[] = {64,25,12,22,11};
System.out.println("Given array"+Arrays.toString(arr));
       sort(arr);
       System.out.println("Sorted array"+Arrays.toString(arr));

}

public static void sort(int[] arr){

for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if(arr[j]>arr[j+1]){
//swap
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}

}

}

}

}

OUTPUT:

Given array[64, 25, 12, 22, 11]

Sorted array[11, 12, 22, 25, 64]

JumpSearch

JumpSearch

package search;
/*JumpSearch is nothing but to divide the array into steps and  search it alongwith steps.*/

/**
 * @author sachin4java@blogspot.com
 *
 */
public class JumpSearch {

public static void main(String[] args) {
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 144, 233, 377, 610};
   int x = 55;
   // Find the index of 'x' using Jump Search
   int index = jumpSearch(arr, x);
   // Print the index where 'x' is located
   System.out.println("\nNumber " + x + " is at index " + index);
}
   public static int jumpSearch(int[] arr, int x)
   {
       int n = arr.length;
 
       // Finding block size to be jumped
       int step = (int)Math.floor(Math.sqrt(n));
 
       // Finding the block where element is
       // present (if it is present)
       int prev = 0;
       while (arr[Math.min(step, n)-1] < x)
       {
           prev = step;
           step += (int)Math.floor(Math.sqrt(n));
           if (prev >= n)
               return -1;
       }
 
       // Doing a linear search for x in block
       // beginning with prev.
       while (arr[prev] < x)
       {
           prev++;
 
           // If we reached next block or end of
           // array, element is not present.
           if (prev == Math.min(step, n))
               return -1;
       }
 
       // If element is found
       if (arr[prev] == x)
           return prev;
 
       return -1;
   }
 

}

OUTPUT:

Number 55 is at index 10

Binary Search

• Binary Search 

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

Steps:

1. Compare x with the middle element. 
2. If x matches with middle element, we return the mid index. 
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half. 
4. Else (x is smaller) recur for the left half. 

complexity of above algorithm is O(logn)
Code:

/** * @author sachin4java@blogspot.com * */ public class BinarySearch { public static void main(String[] args) { int arr[] = {2,3,4,10,40}; int n = arr.length; int x = 10; //*******Recursive approach************************ System.out.println("*******Recursive approach************************"); int result = binarySearchRecursive(arr,0,n-1,x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at index "+result); //*******Ietrative approach************************ System.out.println("*******Ietrative approach************************"); int result1 = binarySearchIterative(arr, x); if (result1 == -1) System.out.println("Element not present"); else System.out.println("Element found at index "+result1); } //*******Recursive approach************************ static int binarySearchRecursive(int arr[], int start, int end, int x) { if (end>=start) { int mid = start + (end - start)/2; // If the element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it can only // be present in left subarray if (arr[mid] > x) return binarySearchRecursive(arr, start, mid-1, x); // Else the element can only be present in right // subarray return binarySearchRecursive(arr, mid+1, end, x); } // We reach here when element is not present in array return -1; } //*******Iterative approach************************ // Returns index of x if it is present in arr[], else // return -1 static int binarySearchIterative(int arr[], int x) { int start = 0, end = arr.length - 1; while (start <= end) { int m = start + (end-start)/2; // Check if x is present at mid if (arr[m] == x) return m; // If x greater, ignore left half if (arr[m] < x) start = m + 1; // If x is smaller, ignore right half else end = m - 1; } // if we reach here, then element was not present return -1; } }

OUTPUT:

*******Recursive approach************************
Element found at index 3
*******Ietrative approach************************
Element found at index 3

Linear Search

Linear Search

Given an array arr[] of n elements, write a function to search a given element x in arr[].

Steps:

Search from left most element to rightmost element one by one.
If element matched, return the index.
If no match found, return -1.

complexity of above algorithm is O(n)

Code:

/** * @author Sachin Rane(sachin4java.blogspot.com) * */ public class LinearSearch { public static void main(String[] args) { int[] arr = new int[5]; arr[0]=5; arr[1]=8; arr[2]=8; arr[3]=2; arr[4]=4; int x=2; int element = search(arr, x); System.out.println("element-->"+element); } static int search(int arr[], int x) { for (int i = 0; i < arr.length; i++) { // Return the index of the element if the element // is found if (arr[i] == x) return i; } // return -1 if the element is not found return -1; } }

OUTPUT:

element-->3