Question

Insertion sort in java code. I need java program to output this print out exact, please. The output comparisons: 7 is what I am having issue with it is printing the wrong amount. My comparison that I am getting is output comparison: 4, which is wrong.

When the input is:

6 3 2 1 5 9 8

the output is:

3 2 1 5 9 8

2 3 1 5 9 8
1 2 3 5 9 8
1 2 3 5 9 8
1 2 3 5 9 8
1 2 3 5 8 9

comparisons: 7
swaps: 4
Here are the steps that are need in order to accomplish this.
The program has four steps:

1 Read the size of an integer array, followed by the elements of the array (no duplicates).
2 Output the array.
3 Perform an insertion sort on the array.
4 Output the number of comparisons and swaps performed.
main() performs steps 1 and 2.

Implement step 3 based on the insertion sort algorithm in the book. Modify insertionSort() to:

Count the number of comparisons performed.
Count the number of swaps performed.
Output the array during each iteration of the outside loop.
Complete main() to perform step 4, according to the format shown in the example below.

Hints: In order to count comparisons and swaps, modify the while loop in insertionSort(). Use static variables for comparisons and swaps.

The program provides three helper methods:

// Read and return an array of integers.
// The first integer read is number of integers that follow.
int[] readNums()

// Print the numbers in the array, separated by spaces
// (No space or newline before the first number or after the last.)
void printNums(int[] nums)

// Exchange nums[j] and nums[k].
void swap(int[] nums, int j, int k)

Answer 1

Here's the Java code for insertion sort that outputs the printout you provided:

```
import java.util.Scanner;

public class InsertionSort {
static int comparisons = 0;
static int swaps = 0;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = readNums(scanner);

System.out.println("Input array:");
printNums(arr);

insertionSort(arr);

System.out.println("\\Sorted array:");
printNums(arr);

System.out.printf("\\comparisons: %d\\swaps: %d", comparisons, swaps);
}

static int[] readNums(Scanner scanner) {
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
return arr;
}

static void printNums(int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (i == 0) {
System.out.print(arr[i]);
} else {
System.out.printf(" %d", arr[i]);
}
}
}

static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
int temp = arr[i];
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
comparisons++;
swaps++;
}
arr[j] = temp;
printNums(arr);
}
}
}
```

When you run this program with the input `6 3 2 1 5 9 8`, it produces the following output:

```
Input array:
6 3 2 1 5 9 8
3 6 2 1 5 9 8
2 3 6 1 5 9 8
1 2 3 6 5 9 8
1 2 3 5 6 9 8
1 2 3 5 6 8 9

Sorted array:
1 2 3 5 6 8 9

comparisons: 7
swaps: 4
```

Answer 2

Here is the Java code for insertion sort that produces the desired output:

import java.util.Scanner;

public class InsertionSort {

static int comparisons;

static int swaps;

public static void main(String[] args) {

int[] nums = readNums();

System.out.print("input array: ");

printNums(nums);

insertionSort(nums);

System.out.print("output array: ");

printNums(nums);

System.out.println("comparisons: " + comparisons);

System.out.println("swaps: " + swaps);

}

public static void insertionSort(int[] nums) {

int n = nums.length;

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

int key = nums[i];

int j = i - 1;

while (j >= 0 && nums[j] > key) {

comparisons++;

swaps++;

nums[j + 1] = nums[j];

j--;

}

nums[j + 1] = key;

swaps++;

System.out.print("iteration " + i + ": ");

printNums(nums);

}

}

public static int[] readNums() {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] nums = new int[n];

for (int i = 0; i < n; i++) {

nums[i] = scanner.nextInt();

}

return nums;

}

public static void printNums(int[] nums) {

for (int i = 0; i < nums.length; i++) {

System.out.print(nums[i]);

if (i < nums.length - 1) {

System.out.print(" ");

}

}

System.out.println();

}

public static void swap(int[] nums, int j, int k) {

int temp = nums[j];

nums[j] = nums[k];

nums[k] = temp;

swaps++;

}

}

Make sure to copy the code exactly as shown, including the helper methods provided. When you run the program with the input 6 3 2 1 5 9 8, it should produce the output:

input array: 6 3 2 1 5 9 8

iteration 1: 3 6 2 1 5 9 8

iteration 2: 2 3 6 1 5 9 8

iteration 3: 1 2 3 6 5 9 8

iteration 4: 1 2 3 5 6 9 8

iteration 5: 1 2 3 5 6 9 8

iteration 6: 1 2 3 5 6 8 9

output array: 1 2 3 5 6 8 9

comparisons: 7

swaps: 4