Write a program to evaluate experimental Library Sort.

 Input: n= 100,200,300,400,500,600,700,800,900,1000
 *  Output: Not successfull, Still working on it
 * 
 *  Visible data fields:
 *  Integers : i,j,r,w,n,begin,end,imid,imin,imax, arr[],arr_new[],
 *
 *  Visible methods:
 *  Rebalance(int arr[])
 *  Sort(int arr[]) //insertion sort execution
 *  BinarySearch 
 *
 *
 *   Remarks
 *   -------
 *   Program executed with runtime errors(exceptions).
 *   Figuring out how to insert gaps into arrays. Learning dynamic programming and vectors for implementations.
 *   
 *************************************************************************/



import static java.lang.Math.log;
import java.util.Arrays;
import java.util.Scanner;

public class libInsert
{
    
    public static void rebalance(int arr[])
    {
        int begin = 0; 
        int end = arr.length;
        
        int r = end;
        int w = end * 2;
        int arr_new[] = new int[ w+1 ];
        
        for ( int i=0; i < w; i++)
            arr_new[i] = 0;

        while(r>=begin)
        {
            arr_new[w+1]= 0;
            arr_new[w] = arr[r];
            r = r - 1;
            w = w - 2;
        }           
        System.out.println("New" + Arrays.toString(arr_new));
    }
      
    /* Insertion Sort function */
    public static void sort( int arr[])
    {
        int N = arr.length;
        int i, j, temp;

        for (i = 1; i< N; i++) 
        {
            j = i;
            temp = arr[i];    
            while (j > 0 && temp < arr[j-1])
            {
                arr[j] = arr[j-1];
                j = j-1;
            }
            arr[j] = temp;            
        }        
    }    

    /* Main method */
    public static void main(String[] args) 
    {
        int n, i, j;
        Scanner scan = new Scanner( System.in );        
        System.out.println("Insertion Sort Test\n");

        /* Accept number of elements */
        System.out.println("Enter number of integer elements");
        n = scan.nextInt();

        /* Create integer array on n elements */
        int arr[] = new int[ n ];
        //int arr_new[] = new int[ n ];

        /* Accept elements */
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();

        /* Call method sort */
        System.out.println("\nEnter new integer element that you want to insert");
            int key = scan.nextInt();
            
        /* producing gaps at randomlly allocated series of integers
        rebalance(arr);  

        int[] arr_null = new int[n];
        int imin = 0;
        for (i = 0; i <n; i ++)
        {
           arr_null[i] = -1;
        }
        
        /* binary search execution of finding numbers where to insert in the tree*/
        for (i = 1; i< Math.floor(log(n) /log (2))+ 1; i++) 
        {
            for ( j = (int) Math.pow(2,i); j< (int) Math.pow(2,i+1); j++)
            {
                int imax = (int) Math.pow(2,i-1);
                while (imin <= imax)
                {
                // calculate the midpoint for roughly equal partition
                 int imid = (imin + imax)/2;
                 if(arr_null[imid] == key)
                 arr[j] = arr_null[imid] = key;
                 // determine which subarray to search
                 else if (arr_null[imid] < key)
                 imin = imid + 1;
                 else         
                 imax = imid - 1;
                 }     
            }
        }    
             
        /* calling sort function to sort the elements*/  
        sort(arr);

        /* Print sorted Array */
        System.out.println("\nElements after sorting ");        
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");            
        System.out.println();                     
    }    
}

Leave a Reply

Your email address will not be published. Required fields are marked *