ISC Practicals and Theory - Insertion Sort

Insertion sort is a sorting technique that builds the sorted array one element at a time, the way a hand of playing cards is arranged. Each new element is taken and inserted into its correct place among the elements already sorted on its left. This program, written in the main method of the class InsertionSort, reads an integer array of 1 to 20 elements, sorts it in ascending order, shows the array after every pass and prints the number of shifts made.

Definition

In insertion sort, arr[0] alone is treated as a sorted part. In pass $i$ (from 1 to $n - 1$), the element key = arr[i] is compared with the sorted elements on its left, starting from arr[i - 1]. Every element greater than key is shifted one place to the right, and key is stored in the gap that is left.

For an array of $n$ elements:

• Number of passes: $n - 1$.
• Best case (already sorted): no element is shifted.
• Worst case (reverse order): pass $i$ shifts $i$ elements, so the total shifts are $1 + 2 + \dots + (n - 1) = \frac{n(n - 1)}{2}$.

Example for 40 30 20 10: pass 1 gives 30 40 20 10, pass 2 gives 20 30 40 10, pass 3 gives 10 20 30 40. Shifts: $1 + 2 + 3 = 6$.

Size constraint: the size $n$ must be from 1 to 20. Any other value is rejected with a message.

Order: the program sorts in ascending order.

Duplicates: the test arr[j] > key is strict, so an element equal to key is not shifted and equal values keep their original order. Duplicates are handled correctly (see the first sample).

Shift count: the program counts every right shift of an element, not swaps.

Algorithm

1. Read the size n. If it is not from 1 to 20, print an error message and stop.
2. Read the n elements into the array arr and set shifts = 0. Print the original array.
3. For i from 1 to n - 1, the part arr[0..i-1] is already sorted:
   • store arr[i] in key, the element to be inserted, and set j = i - 1;
   • while j >= 0 and arr[j] > key, shift arr[j] one place to the right (arr[j + 1] = arr[j]), add 1 to shifts and decrease j. The comparison is strictly greater, so equal elements are not crossed;
   • place the key in the gap, arr[j + 1] = key, and print the array after this pass.
4. Print the sorted array and the number of shifts.

Program

In main, the outer for loop takes each key and the inner while loop shifts the larger elements to the right. A small for loop prints the array each time it is shown.

import java.util.Scanner;
class InsertionSort
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);        // reads input from the keyboard
        System.out.print("Enter the size of the array (1 to 20): ");
        int n = sc.nextInt();                       // the size of the array
        if (n < 1 || n > 20)                        // size outside 1 to 20 is invalid
        {
            System.out.println("Invalid size. Size must be between 1 and 20.");
        }
        else
        {
            int arr[] = new int[n];                 // the elements of the array
            System.out.println("Enter " + n + " elements:");
            for (int i = 0; i < n; i++)             // reads one element per turn
                arr[i] = sc.nextInt();
            int shifts = 0;                         // counts the number of times an element is shifted right
            System.out.print("Original array: ");
            for (int k = 0; k < n; k++)
                System.out.print(arr[k] + " ");
            System.out.println();
            for (int i = 1; i < n; i++)             // arr[0..i-1] is already sorted
            {
                int key = arr[i];                   // element to be inserted into the sorted part
                int j = i - 1;                      // position of the last sorted element
                while (j >= 0 && arr[j] > key)      // strictly greater, so equal elements are not crossed
                {
                    arr[j + 1] = arr[j];            // shift the larger element one place right
                    shifts++;
                    j--;
                }
                arr[j + 1] = key;                   // place the key in the gap
                System.out.print("After pass " + i + ": ");
                for (int k = 0; k < n; k++)
                    System.out.print(arr[k] + " ");
                System.out.println();
            }
            System.out.print("Sorted array: ");
            for (int k = 0; k < n; k++)
                System.out.print(arr[k] + " ");
            System.out.println();
            System.out.println("Number of shifts: " + shifts);
        }
    }
}

Variable description table

Sample input and output

Enter the size of the array (1 to 20): 6
Enter 6 elements:
9 5 1 4 3 5
Original array: 9 5 1 4 3 5 
After pass 1: 5 9 1 4 3 5 
After pass 2: 1 5 9 4 3 5 
After pass 3: 1 4 5 9 3 5 
After pass 4: 1 3 4 5 9 5 
After pass 5: 1 3 4 5 5 9 
Sorted array: 1 3 4 5 5 9 
Number of shifts: 9

Enter the size of the array (1 to 20): 5
Enter 5 elements:
10 20 30 40 50
Original array: 10 20 30 40 50 
After pass 1: 10 20 30 40 50 
After pass 2: 10 20 30 40 50 
After pass 3: 10 20 30 40 50 
After pass 4: 10 20 30 40 50 
Sorted array: 10 20 30 40 50 
Number of shifts: 0

Enter the size of the array (1 to 20): 4
Enter 4 elements:
40 30 20 10
Original array: 40 30 20 10 
After pass 1: 30 40 20 10 
After pass 2: 20 30 40 10 
After pass 3: 10 20 30 40 
Sorted array: 10 20 30 40 
Number of shifts: 6

Enter the size of the array (1 to 20): 1
Enter 1 elements:
15
Original array: 15 
Sorted array: 15 
Number of shifts: 0

Enter the size of the array (1 to 20): 0
Invalid size. Size must be between 1 and 20.

Dry run

Input: n = 4, elements 40 30 20 10.

The sorted array is 10 20 30 40 with 6 shifts, which matches the third sample run.

Variations

1. Descending order "Sort an integer array in descending order using the insertion sort technique."
2. Strings "Sort an array of names in alphabetical order using the insertion sort technique."
3. Insert into a sorted array "Insert a given element into an already sorted array so that the array remains sorted."
4. Count comparisons and shifts "Sort an array using insertion sort and display the number of comparisons and shifts made."