Question

Please create a method or class to test my Insertion Sort algorithm by providing a complete test with n = 2, 4, … , up to 2^16 .

public static void insertionSort(int a[])

       {

             int n = a.length;

            

             for (int i = 1; i < n; i++)

             {

                    int target = a[i];

                    int j = i - 1;

                   

                    while (j >= 0 && target < a[j])

                    {

                           a[j + 1] = a[j];

                           j--;

                    }

                    a[j+1] = target;

              }

       }

Answer 1

import java.util.Random;

public class InsertionSort {

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

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

            while (j >= 0 && target < a[j])
            {
                a[j + 1] = a[j];
                j--;
            }
            a[j+1] = target;
        }
    }

    public static boolean isSorted(int a[]) {
        for(int i = 1; i < a.length; ++i) {
            if(a[i] < a[i-1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 2;
        Random random = new Random();
        int max = Integer.MAX_VALUE;
        for(int i = 0; i < 16; ++i) {
            int arr[] = new int[n];
            for(int j = 0; j < n; ++j) {
                arr[j] = random.nextInt(max);
            }
            insertionSort(arr);
            if(isSorted(arr)) {
                System.out.println("Sorted successfully for n = " + n);
            } else {
                System.out.println("Sorted unsuccessfully for n = " + n);
            }
            n *= 2;
        }
    }

}

successfully for n-2 Sorted successfully for n-4 Sorted successfully for n- 8 Sorted successfully for n 1 Sorted Sorted Sorted successfully for n- 128 Sorted successfully for n - 2 Sorted Sorted successfully for n 1024 Sorted Sorted successfully for n-4096 successfully for n 32 successfully forn- 64 successfully for n -512 successfully for n-2048 successfully for n- 8192 Sorted successfully for n 16384 Sorted successfully for n- 32768 Sorted successfully for n-65536 Process finished with exit code 0