Question

in java program code Insertion sort The program has four steps: Read the size of an integer array, followed by the elements of the array (no duplicates). Output the array. Perform an insertion sort on the array. 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) Ex: 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

Answer 1

To implement the insertion sort algorithm, you need to modify the insertionSort() method in Java. Perform the insertion sort on the array and count the number of comparisons and swaps using static variables. Finally, output the sorted array and the number of comparisons and swaps performed.

Step-by-step explanation:

To implement the insertion sort algorithm in java, you need to modify the insertionSort() method. You will need to count the number of comparisons and swaps performed in separate static variables. Additionally, you need to output the array during each iteration of the outside loop. Here is the modified insertionSort() method:

public static void insertionSort(int[] nums) {
int n = nums.length;
int comparisons = 0;
int swaps = 0;
for (int i = 1; i < n; i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
comparisons += (i - j - 1);
swaps += (i - j - 1);
printNums(nums);
}
System.out.println("comparisons: " + comparisons);
System.out.println("swaps: " + swaps);
}

In the main() method, you need to perform steps 1 and 2, and then call the insertionSort() method passing the array as an argument. Finally, output the array, number of comparisons, and swaps. Here is the completed main() method:

public static void main(String[] args) {
int[] nums = readNums();
printNums(nums);
insertionSort(nums);
printNums(nums);
}

With the given input 6 3 2 1 5 9 8, the output will be:

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

Answer 2

Here's a sample Java program that implements the insertion sort algorithm and counts the number of comparisons and swaps performed:

import java.util.Scanner;

public class InsertionSort {

// Static variables to count the number of comparisons and swaps

static int numComparisons = 0;

static int numSwaps = 0;

public static void main(String[] args) {

// Step 1: Read the size of the array and the elements

int[] nums = readNums();

// Step 2: Print the input array

printNums(nums);

// Step 3: Perform insertion sort

insertionSort(nums);

// Step 4: Print the sorted array and the number of comparisons and swaps

printNums(nums);

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

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

}

// Read and return an array of integers

// The first integer read is the number of integers that follow

static int[] readNums() {

Scanner input = new Scanner(System.in);

int n = input.nextInt();

int[] nums = new int[n];

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

nums[i] = input.nextInt();

}

return nums;

}

// Print the numbers in the array, separated by spaces

// (No space or newline before the first number or after the last.)

static void printNums(int[] nums) {

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

System.out.printf("%d", nums[i]);

if (i < nums.length - 1) {

System.out.print(" ");

}

}

System.out.println();

}

// Exchange nums[j] and nums[k]

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

int temp = nums[j];

nums[j] = nums[k];

nums[k] = temp;

}

// Perform an insertion sort on the array nums

static void insertionSort(int[] nums) {

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

// Insert nums[i] into the sorted subarray nums[0:i-1]

int j = i;

while (j > 0 && nums[j] < nums[j-1]) {

swap(nums, j, j-1);

numComparisons++;

numSwaps++;

j--;

}

printNums(nums); // Output the array during each iteration

numComparisons++; // Increment the number of comparisons

}

}

}