Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:
for i = 2 to N
j = i
while j > 1 and a[j] < a[j - 1]
swap a[j] and a[j - 1]
j = j-1
The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in its right position.
As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.
Input:
The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].
Output:
Output T lines, containing the required answer for each test case.
Constraints:
1 <= T <= 5
1 <= N <= 100000
1 <= a[i] <= 1000000
Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2
Sample Output:
0
4
ALSO : The given algorithm should not take more than 5 sec to execute for the maximum input size.
Courtesy : interviewstreet.com
for i = 2 to N
j = i
while j > 1 and a[j] < a[j - 1]
swap a[j] and a[j - 1]
j = j-1
The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in its right position.
As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.
Input:
The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].
Output:
Output T lines, containing the required answer for each test case.
Constraints:
1 <= T <= 5
1 <= N <= 100000
1 <= a[i] <= 1000000
Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2
Sample Output:
0
4
ALSO : The given algorithm should not take more than 5 sec to execute for the maximum input size.
Courtesy : interviewstreet.com
The solution to the problem :-
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution {
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in))
static long count=0;
public static void main(String[] args) throws IOException{
int noOfTestCases=Integer.parseInt(bf.readLine());
for(int t=0; t<noOfTestCases;t++){
int length=Integer.parseInt(bf.readLine());
int[] myArray=new int[length];
String[] input=bf.readLine().split(" ");
for(int i=0; i<length;i++){
myArray[i]=Integer.parseInt(input[i]);
}
mergeSort(myArray, 0, myArray.length-1);
System.out.println(count);
count =0;
}
}
public static void mergeSort(int[] A, int p, int r) {
if(p<r){
int q=(p+r)/2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
private static void merge(int[] A, int p, int q, int r) {
int n1=q-p+1;
int n2=r-q;
int[] L=new int[n1];
int[] R=new int[n2];
for(int i=0; i<L.length;i++){
L[i]=A[p+i];
}
for(int j=0; j<R.length; j++){
R[j]=A[q+j+1];
}
int i=0;
int j=0;
for(int k=p; k<=r; k++){
if(i>=L.length){
A[k]=R[j];
j++;
}
else if(j>=R.length){
A[k]=L[i];
i++;
}
else if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
count+=n1-i;
j++;
}
}
}
}
The time complexity of the algorithm comes out to be 𝛩(nlogn). So our algorithm scales appropriately and is within the given time constraint.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution {
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in))
static long count=0;
public static void main(String[] args) throws IOException{
int noOfTestCases=Integer.parseInt(bf.readLine());
for(int t=0; t<noOfTestCases;t++){
int length=Integer.parseInt(bf.readLine());
int[] myArray=new int[length];
String[] input=bf.readLine().split(" ");
for(int i=0; i<length;i++){
myArray[i]=Integer.parseInt(input[i]);
}
mergeSort(myArray, 0, myArray.length-1);
System.out.println(count);
count =0;
}
}
public static void mergeSort(int[] A, int p, int r) {
if(p<r){
int q=(p+r)/2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
private static void merge(int[] A, int p, int q, int r) {
int n1=q-p+1;
int n2=r-q;
int[] L=new int[n1];
int[] R=new int[n2];
for(int i=0; i<L.length;i++){
L[i]=A[p+i];
}
for(int j=0; j<R.length; j++){
R[j]=A[q+j+1];
}
int i=0;
int j=0;
for(int k=p; k<=r; k++){
if(i>=L.length){
A[k]=R[j];
j++;
}
else if(j>=R.length){
A[k]=L[i];
i++;
}
else if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
count+=n1-i;
j++;
}
}
}
}
The time complexity of the algorithm comes out to be 𝛩(nlogn). So our algorithm scales appropriately and is within the given time constraint.