searching

12 B. INSERTION SORT

package sorting;

public class InsertionSort {

 public static void insertionSort(int[] array) { 
     int n = array.length; 

     for (int i = 1; i < n; i++) { 
         int key = array[i]; 
         int j = i - 1; 

// Move elements of array[0..i-1] that are greater than key to one position ahead
of their current position
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
// Place the key in its correct position
array[j + 1] = key;
}
}

 public static void main(String[] args) { 
     int[] array = {64, 25, 12, 22, 11}; 
      
     System.out.println("Original array:");         
     for(int i=0;i<array.length;i++) { 
      System.out.print(array[i]+" "); 
     } 

     insertionSort(array); 

     System.out.println("\nSorted array:"); 
     for(int i=0;i<array.length;i++) { 
      System.out.print(array[i]+" "); 
     } 

}
}

12 A. SELECTION SORT

package sorting;

public class SelectionSort {
public static void selectionSort(int[] array) {
int n = array.length;

     // One by one move the boundary of the unsorted subarray 
     for (int i = 0; i < n - 1; i++) { 
         // Find the minimum element in the unsorted array 
         int minIndex = i; 
         for (int j = i + 1; j < n; j++) { 
             if (array[j] < array[minIndex]) { 
                 minIndex = j; 
             } 
         } 
         // Swap the found minimum element with the first element 
         int temp = array[minIndex]; 
         array[minIndex] = array[i]; 
         array[i] = temp; 
     } 
 } 

 public static void main(String[] args) { 
     int[] array = {64, 25, 12, 22, 11}; 
      
     System.out.println("Original array:");         
     for(int i=0;i<array.length;i++) { 
      System.out.print(array[i]+" "); 
     } 

     selectionSort(array); 

     System.out.println("\nSorted array:"); 
     for(int i=0;i<array.length;i++) { 
      System.out.print(array[i]+" "); 
     } 

}
}

11 B. BINARY SEARCH

package searching;

public class binarySearch {
// Function to perform binary search
static void BinarySearch(int[] array, int key) {
int low = 0;
int high = array.length - 1;

     while (low <= high) { 
         int mid = (low + high) / 2; 

         // Check if the key is present at the middle 
         if (array[mid] == key) { 

System.out.println("Element " + key + " found at index " + mid);
return;
}

         // If the key is greater, ignore the low half 
         if (array[mid] < key) { 
             low = mid + 1; 
         } 

         // If the key is smaller, ignore the high half 
         else { 
             high = mid - 1; 
         } 
     } 

System.out.println("Element " + key + " not found in the array");
}

 public static void main(String[] args) { 
     int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
     int key = 5; 

     // Perform binary search 
     BinarySearch(array, key); 
           
 } 

}

11 A. LINEAR SEARCH

package searching;
public class linearSearch {
// Function to perform linear search
static void LinearSearch(int[] array, int key) {
for (int i = 0; i < array.length; i++) {
if (array[i] == key) {
System.out.println("Element " + key + " found at index " + i);
return;
}
}
System.out.println("Element " + key + " not found in the array");
}
public static void main(String[] args) {
int[] array = {1, 5, 9, 2, 7, 3, 8, 4, 6};
int key = 7;
// Perform linear search
LinearSearch(array, key);
}
}