Insertion sort Read in a sequence of 32-bit signed integers (one per line). The
ID: 3923198 • Letter: I
Question
Insertion sort Read in a sequence of 32-bit signed integers (one per line). The first line contains a value n, which is not part of the sequence, indicating how many further lines of integers need to be sorted. Implement insertion sort on an array to output the sequence in increasing sort (numerical) order, count the number of moves required for the sort and how many additional inversions would be needed to reach the maximum number of inversions for the given input and size. Name your program task1.py (or .java/.cpp depending on language choice).
Example input
3
7
1
2
which produces output
1
2
7
moves:2
additionalinversions:1
Explanation / Answer
Code:
package insertion_sort;
import java.util.Scanner;
public class Insertion_sort {
static int moves=0;
public static void main(String[] args) {
int[] a=new int[20];
Scanner sc=new Scanner(System.in);
//Value n
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
// call insertion sort
Insertionsort(a,n);
for(int i=0;i<n;i++)
{
System.out.println( a[i]);
}
System.out.println("Moves :"+moves);
int y=n;
// Maximum number of inversion
y=(y*(y-1))/2;
// Number of additional inversion
int addi_inversion=y-moves;
System.out.println("additionalInversion :"+addi_inversion);
}
private static void Insertionsort(int[] a, int n) {
int i,j,key;
for(j=1;j<n;j++)
{
key=a[j];
i=j-1;
while((i>-1)&&(a[i]>key))
{
a[i+1]=a[i];
i=i-1;
moves++;
}
a[i+1]=key;
}
}
}
Output:
run:
3
7
1
2
1
2
7
Moves :2
additionalInversion :1
BUILD SUCCESSFUL (total time: 7 seconds)