ISC Practicals and Theory - Insertion Sort (OOP)

Insertion sort builds the sorted array one element at a time: each new element is inserted into its correct place among the already sorted elements on its left. This version is written in an object-oriented style: the class InsertionSort has a parameterised constructor, and separate methods read the array, insert one element, sort and display. It reads 1 to 20 integers, sorts them in ascending order, shows the array after every pass and prints the number of shifts.

Definition

In pass $i$ (from 1 to $n - 1$), the element key = arr[i] is compared with the sorted elements on its left. Each element greater than key is shifted one place right, and key is stored in the gap. An array of $n$ elements needs $n - 1$ passes; a reverse-ordered array needs the most shifts, $\frac{n(n - 1)}{2}$, and a sorted array needs none.

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 (6 shifts).

Size constraint: the size must be from 1 to 20; main checks this before the object is created.

Order: ascending.

Duplicates: arr[j] > key is strict, so equal values are not crossed and duplicates are sorted correctly.

Shift count: every right shift of an element is counted, not swaps.

Algorithm

1. In main, read the size into size. If it is less than 1 or more than 20, print an error message and stop.
2. Create the object ob with new InsertionSort(size). The constructor sets n, creates arr of that size and sets shifts to 0.
3. Call readArray(sc) to read the $n$ elements with a for loop.
4. Call display("Original array: ").
5. Call sort(): for i from 1 to $n - 1$, call insert(i) and then display("After pass ...").
6. insert(p) does the work of one pass:
   • Set key = arr[p] and j = p - 1.
   • While j >= 0 and arr[j] > key: copy arr[j] to arr[j + 1], increase shifts and decrease j.
   • Store key at arr[j + 1].
7. Call display("Sorted array: ") and showShifts().

Program

Each method does one job: the constructor sets up the array, readArray() reads it, insert() places one element in the sorted part, sort() controls the passes, display() prints and showShifts() reports the count.

import java.util.Scanner;

/**
 * Class InsertionSort stores an integer array and sorts it in
 * ascending order using the insertion sort technique.
 */
class InsertionSort
{
    int arr[];      // stores the elements of the array
    int n;          // stores the size of the array
    int shifts;     // counts the number of times an element is shifted right

    /**
     * Parameterised constructor: sets the size and creates the array.
     * size : number of elements of the array
     */
    InsertionSort(int size)
    {
        n = size;
        arr = new int[n];
        shifts = 0;
    }

    /**
     * Reads the n elements of the array from the keyboard.
     * sc : Scanner object used to read the elements
     */
    void readArray(Scanner sc)
    {
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++)             // reads one element per turn
            arr[i] = sc.nextInt();
    }

    /**
     * Displays the array on one line, preceded by the given heading.
     * msg : the heading to be printed before the elements
     */
    void display(String msg)
    {
        System.out.print(msg);
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    /**
     * Inserts arr[p] into its correct place in the sorted part arr[0] to arr[p-1].
     * p : index of the element to be inserted
     */
    void insert(int p)
    {
        int key = arr[p];                       // element to be inserted
        int j = p - 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
    }

    /**
     * Sorts the array in ascending order and displays it after every pass.
     */
    void sort()
    {
        for (int i = 1; i < n; i++)             // arr[0..i-1] is already sorted
        {
            insert(i);
            display("After pass " + i + ": ");
        }
    }

    /**
     * Displays the number of shifts made.
     */
    void showShifts()
    {
        System.out.println("Number of shifts: " + shifts);
    }

    /**
     * main reads and validates the size, creates the object
     * and calls the methods in order.
     * args : command line arguments (not used)
     */
    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 size = sc.nextInt();                // size entered by the user
        if (size < 1 || size > 20)              // size outside 1 to 20 is invalid
        {
            System.out.println("Invalid size. Size must be between 1 and 20.");
            return;
        }
        InsertionSort ob = new InsertionSort(size);     // object of the class
        ob.readArray(sc);
        ob.display("Original array: ");
        ob.sort();
        ob.display("Sorted array: ");
        ob.showShifts();
    }
}

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: size = 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."