Question

Java programming:

Write a method, remove, that takes three parameters: an array of integers, the length of the array, and an integer called removeItem. The method should find and delete the first occurrence of removeItem in the array. If the value does not exist or the array is empty, output an appropriate message. (Note that after deleting the element, the array size is reduced by 1.) You may assume that the array is unsorted.

Now re-do this exercise and name it ExInsertionSort. This time use an insertion sort as given in this chapter to sort the array and then remove the item with the array sorted. Create a method for the insertion sort. Please only provide the code for ExInsertionSort.

Answer 1

public class ExInsertionSort {

    /*Function to sort array using insertion sort*/
    public static void Insertionsort(int arr[])
    {
        int n = arr.length;
        for (int i=1; i=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }

}

import java.util.Scanner;

public class RemoveFromSorted
{
    // binary search
    static int binarySearch(int arr[], int low, int high, int key)
    {
        if (high < low)
            return -1;
        int mid = (low + high)/2;
        if (key == arr[mid])
            return mid;
        if (key > arr[mid])
            return binarySearch(arr, (mid + 1), high, key);
        return binarySearch(arr, low, (mid -1), key);
    }

    /* Function to delete an element */
    static int removeItem(int arr[], int n, int key)
    {
        // Find position of element to be deleted
        int pos = binarySearch(arr, 0, n-1, key);

        if (pos==-1)
        {
            System.out.println("Element not found");
            return n;
        }

        // Deleting element
        int i;
        for (i=pos; i arr[j+1])
                {
                    // swap temp and arr[i]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
    }

    /* Driver program to test above function */
    public static void main (String[] args)
    {

        int i;
        int arr[] = {20, 10, 50, 40, 70, 89};

        int n = arr.length;

        Scanner sc = new Scanner(System.in);
        System.out.print("\nEnter value to remove: ");
        int key = sc.nextInt();

        ExInsertionSort.Insertionsort(arr); // sorting

        System.out.print("Array before deletion:\n");
        for (i=0; iSystem.out.print(arr[i] + " ");

        System.out.println();

        n = removeItem(arr, n, key);

        System.out.print("\n\nArray after deletion:\n");
        for (i=0; iSystem.out.print(arr[i] + " ");
    }
}

Output:

Enter value to remove: 54
Array before deletion:
10 20 40 50 70 89
Element not found

Array after deletion:
10 20 40 50 70 89
Process finished with exit code 0