[go: up one dir, main page]
Scribd
Upload
6 views3 pages

Intertion Sort

The document describes an insertion sort algorithm in Java. It reads in an array of numbers, sorts the numbers using insertion sort, and outputs the number of comparisons and swaps made during the sorting process.

Uploaded by

Lê Tiến Phát
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views3 pages

Intertion Sort

The document describes an insertion sort algorithm in Java. It reads in an array of numbers, sorts the numbers using insertion sort, and outputs the number of comparisons and swaps made during the sorting process.

Uploaded by

Lê Tiến Phát
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

import java.util.

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(System.in);
int size = scnr.nextInt(); // Read array size
int[] numbers = new int[size]; // Create array
for (int i = 0; i < size; ++i) { // Read the numbers
numbers[i] = scnr.nextInt();
}
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 < nums.length; ++i)
{
System.out.print(nums[i]);
if (i < nums.length - 1)
{
System.out.print(" ");
}
}
System.out.println();
}

// 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 < numbers.length; ++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);
System.out.println();

// Step 3: Sort the numbers array


insertionSort(numbers);
System.out.println();
// step 4
/* TODO: Output the number of comparisons and swaps performed */
// Modified:
// Display the number of comparisons and number of swaps
System.out.println("comparisons: " + countComparisons);
System.out.println("swaps: " + countSwaps);
}
}

You might also like