Using pen and paper, write out the contents of the array after each pass of the

Question

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. int[] exampleArr = {5, 91, 19, 7, 46, 2, 8, 29, 14}; insertionSort (exampleArr); [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

Here goes the contents of the arrays after step by step pass in insertion sort algorithm.

int[] arr1={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,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}

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

{2,14,17,23,31,36,42,47,49}

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

{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}

Java program for the insertion sort algorithm is given below

public class InsertionSort {
public static void insertionSort(int array[]) {
int n = array.length;
for (int i = 1; i < n; i++) {
int temp = array[i];
int j = i-1;
while ( (j > -1) && ( array [j] > temp ) ) {
array [j+1] = array [j];
j--;
}
array[j+1] = temp;

for(int k:array){
System.out.print(k+" ");
}
System.out.println();
  
}
}

public static void main(String a[]){
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};
  
System.out.println("Before Insertion Sort of array1");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
  
insertionSort(arr1);

System.out.println("After Insertion Sort of array1");
for(int i:arr1){
System.out.print(i+" ");
}
   System.out.println();
   System.out.println("Before Insertion Sort of array2");
for(int i:arr2){
System.out.print(i+" ");
}
System.out.println();
  
insertionSort(arr2);   

System.out.println("After Insertion Sort of array2");
for(int i:arr2){
System.out.print(i+" ");
}
   System.out.println();
   System.out.println("Before Insertion Sort of array3");
for(int i:arr3){
System.out.print(i+" ");
}
System.out.println();
  
insertionSort(arr3);

System.out.println("After Insertion Sort of array3");
for(int i:arr3){
System.out.print(i+" ");
}
}
}

The given program sort the 3 given arrays arr1 ,arr2, arr3 using insertion sort algorithm.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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