Insertion Sort - Part 1

Given problem statment

Sorting

One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort

These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with an already sorted list.

Insert element into sorted list

Given a sorted list with an unsorted number in the rightmost cell, can you write some simple code to insert into the array so that it remains sorted?

Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

Guideline: You can copy the value of e to a variable and consider its cell “empty”. Since this leaves an extra cell empty on the right, you can shift everything over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with e.

Input Format

There will be two lines of input: n - the size of the array arr - the array containing n-1 sorted integers and one unsorted integer e in the rightmost cell

Output Format

On each line, output the entire array every time an item is shifted in it.

problem explanation

we will be given an sorted array of integers except for the last element we need to takes that last element and perform insertion sort on the array. Starting from the last element and we need to print the array state at each step of the insertion sort.

Link to the problem on hackerrank

java solution explanation

We will have two methods called printArray to print the array and also sort to sort the array after reading the array values our main function will call the sort method.

In the sort method we will have a key variable store the last value of the array then we will have a for loop in which will iterate over the array from the before position to the last element and will compare it to the key if the key is greater than or equal to the current element we will put key in that elements position and print the array and return to exit the method.

if the current element is greater than the key we will assign the element before current element with the value of the current element

If the loop completes without exiting we will assign the key value of the first element of the array and print the array

Solution in java

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        sort(n, arr);
        sc.close();
    }

    public static void sort(int n, int[] arr) {
        int key = arr[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            if (arr[j] <= key) {
                arr[j + 1] = key;
                printArray(arr);
                return;
            } else {
                arr[j + 1] = arr[j];
                printArray(arr);
            }
        }
        arr[0] = key;
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}