# Nearly Sorted Algorithm

QUESTION

Given an array of n elements, where each element is at most k away from its target position. The task is to print array in sorted form.\n\nInput:\nFirst line consists of T test cases. First line of every test case consists of two integers N and K, denoting number of elements in array and at most k positions away from its target position respectively. Second line of every test case consists of elements of array.\n\nOutput:\nSingle line output to print the sorted array.\n\nConstraints:\n1<=T<=100\n1<=N<=100\n1<=K<=N.

“TESTCASE_1”: “2\n3\n2 1 3\n6\n2 6 3 12 56 8\n###—###SEPERATOR—###—\n1 2 3 \n2 3 6 8 12 56”, “TESTCASE_2”: “2\n3\n4 2 6\n6\n2 4 3 7 6 8\n###—###SEPERATOR—###—\n2 4 6 \n2 3 4 6 7 8”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include <iostream>
using namespace std;
void swap(int *xp,int *yp){
int temp = *xp;
*xp=*yp;
*yp=temp;
}
int main()
{
int t,k,j;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a[n];
for(int k=0;k<n;k++){
cin>>a[k];
}
for(j=0;j<n-1;j++){
for(k=0;k<n-j-1;k++){
if(a[k]>a[k+1]){
swap(&a[k],&a[k+1]);
}
}
}
for(int k=0;k<n;k++){
cout<<a[k]<<" ";
}
cout<<endl;
}

return 0;
}``````