need help with this program in java Using pen and paper, write out the contents

Question

need help with this program in java

Using pen and paper, write out the contents of the array after each pass of the insertion sort algorithm for the following arrays:

int[] arr1 = {14, 28, 17, 74, 32, 16, 5, 9, 41}

int[] arr2 = {2, 14, 17, 23, 31, 36, 42, 47, 49}

int[] arr3 = {97, 81, 74, 68, 62, 54, 50, 41, 13}

Implement the insertion sort algorithm in Java and write out the state of the array after each pass.

Use your implementation to check your pen and paper work.

example code:

int[] exampleArr = {5, 91, 19, 7, 46, 2, 8, 29, 14};

insertionSort(exampleArr);

Example output

[5, 91, 19, 7, 46, 2, 8, 29, 14]

[5, 19, 91, 7, 46, 2, 8, 29, 14]

[5, 7, 19, 91, 46, 2, 8, 29, 14]

[5, 7, 19, 46, 91, 2, 8, 29, 14]

[2, 5, 7, 19, 46, 91, 8, 29, 14]

[2, 5, 7, 8, 19, 46, 91, 29, 14]

[2, 5, 7, 8, 19, 29, 46, 91, 14]

[2, 5, 7, 8, 14, 19, 29, 46, 91]

Explanation / Answer

import java.util.Arrays;

/**
*
* @author Sam
*/
public class InsertSort {

    public static void main(String[] args) {
        int[] arr1 = {14, 28, 17, 74, 32, 16, 5, 9, 41};

        int[] arr2 = {2, 14, 17, 23, 31, 36, 42, 47, 49};

        int[] arr3 = {97, 81, 74, 68, 62, 54, 50, 41, 13};

        int[] exampleArr = {5, 91, 19, 7, 46, 2, 8, 29, 14};
        System.out.println(Arrays.toString(exampleArr));
        insertionSort(exampleArr);
        System.out.println(" " + Arrays.toString(arr1));
        insertionSort(arr1);
        System.out.println(" " + Arrays.toString(arr2));
        insertionSort(arr2);
        System.out.println(" " + Arrays.toString(arr3));
        insertionSort(arr3);
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int element = arr[i]; //selected element
            int j;
            for (j = i - 1; j >= 0; j--) { //shift array if required
                if (element < arr[j]) {
                    arr[j + 1] = arr[j];
                } else { //we got the apt position to place the 'element'
                    break;
                }
            }
            arr[j + 1] = element; //place element
            System.out.println(Arrays.toString(arr)); //end if pass, print the array
        }
    }
}

OUTPUT:

[5, 91, 19, 7, 46, 2, 8, 29, 14]
[5, 91, 19, 7, 46, 2, 8, 29, 14]
[5, 19, 91, 7, 46, 2, 8, 29, 14]
[5, 7, 19, 91, 46, 2, 8, 29, 14]
[5, 7, 19, 46, 91, 2, 8, 29, 14]
[2, 5, 7, 19, 46, 91, 8, 29, 14]
[2, 5, 7, 8, 19, 46, 91, 29, 14]
[2, 5, 7, 8, 19, 29, 46, 91, 14]
[2, 5, 7, 8, 14, 19, 29, 46, 91]

[14, 28, 17, 74, 32, 16, 5, 9, 41]
[14, 28, 17, 74, 32, 16, 5, 9, 41]
[14, 17, 28, 74, 32, 16, 5, 9, 41]
[14, 17, 28, 74, 32, 16, 5, 9, 41]
[14, 17, 28, 32, 74, 16, 5, 9, 41]
[14, 16, 17, 28, 32, 74, 5, 9, 41]
[5, 14, 16, 17, 28, 32, 74, 9, 41]
[5, 9, 14, 16, 17, 28, 32, 74, 41]
[5, 9, 14, 16, 17, 28, 32, 41, 74]

[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]
[2, 14, 17, 23, 31, 36, 42, 47, 49]

[97, 81, 74, 68, 62, 54, 50, 41, 13]
[81, 97, 74, 68, 62, 54, 50, 41, 13]
[74, 81, 97, 68, 62, 54, 50, 41, 13]
[68, 74, 81, 97, 62, 54, 50, 41, 13]
[62, 68, 74, 81, 97, 54, 50, 41, 13]
[54, 62, 68, 74, 81, 97, 50, 41, 13]
[50, 54, 62, 68, 74, 81, 97, 41, 13]
[41, 50, 54, 62, 68, 74, 81, 97, 13]
[13, 41, 50, 54, 62, 68, 74, 81, 97]

I have provided you with both code and output for each of the arrays given above, I hope you like the code. In case of any difficulties, please feel free to comment in the comment section

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.