import [Link].
Scanner;
public class InsertionSortDemo
{
// Read and return an array of integers.
// The first integer read is number of integers that follow.
private static int[] readNums()
{
//Create a Scanner class's object for read input
Scanner scnr = new Scanner([Link]);
int size = [Link](); // Read array size
int[] numbers = new int[size]; // Create array
for (int i = 0; i < size; ++i) { // Read the numbers
numbers[i] = [Link]();
}
return numbers;
}
// Print the numbers in the array, separated by spaces
// (No space or newline before the first number or after the last.)
private static void printNums(int[] nums)
{
for (int i = 0; i < [Link]; ++i)
{
[Link](nums[i]);
if (i < [Link] - 1)
{
[Link](" ");
}
}
[Link]();
}
// Exchange nums[j] and nums[k].
private static void swap(int[] nums, int j, int k)
{
int temp = nums[j];
nums[j] = nums[k];
nums[k] = temp;
}
// Sort numbers
/* TODO: Count comparisons and swaps. Output the array at the end of each
iteration. */
//Modification:
// Declare the countComparisons and countSwaps variable here and initialize
with zero
private static int countComparisons=0;
private static int countSwaps=0;
public static void insertionSort(int[] numbers)
{
int i;
int j;
// Modification:
// No need to declare comparison and swaps variable here
// int comparisons = 0;
// int swaps = 0;
for (i = 1; i < [Link]; ++i)
{
j = i;
// Insert numbers[i] into sorted part,
// stopping once numbers[i] is in correct position
while (j > 0 && numbers[j] < numbers[j - 1])
{
// Modification: declare the countComparisons here
++countComparisons;
// Swap numbers[j] and numbers[j - 1]
swap(numbers, j, j - 1);
// Modification:
// No need to declare the increment swap
// variable declare countSwaps rather than swaps
++countSwaps;
--j;
}
//Modification:
// Check the condition when j is greater than 0
if (j > 0)
// Increment count comparison
++countComparisons;
// Call here, printNums method
printNums(numbers);
}
}
//Create a main function of the program
public static void main(String[] args)
{
// Step 1: Read numbers into an array
int[] numbers = readNums();
// Step 2: Output the numbers array
printNums(numbers);
[Link]();
// Step 3: Sort the numbers array
insertionSort(numbers);
[Link]();
// step 4
/* TODO: Output the number of comparisons and swaps performed */
// Modified:
// Display the number of comparisons and number of swaps
[Link]("comparisons: " + countComparisons);
[Link]("swaps: " + countSwaps);
}
}
