# Sorting of partially or k sorted array in C++

In this tutorial, we learn how to sort partially or nearly sorted array in  C++. We have given array in which each element is at most k position away from its sorted position.

```for example
K= 3
arr[]={2,1,3}
k=3
arr[]={2,6,3,12,56,8}

```

Here we will solve this problem in three ways.

### Bubble Sort on partially or k sorted array in C++

```#include <iostream>
using namespace std;

int main() {

int arr[6]={2,6,3,12,56,8};

int n=6;

for(int i=0;i<n-1;i++)
{

for(int j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;
}

}

}

for(int i=0;i<n;i++)
{

cout << arr[i] <<endl;

}

return 0;
}```
```output
2
3
6
8
12
56```

Here in bubble sort time complexity O(n*n) so definitely this, not an efficient way to solve this problem.

### Insertion  Sort on partially or k sorted array in C+

```#include <iostream>
using namespace std;

int main() {

int arr[6]={2,6,3,12,56,8};

int n=6;

int x;

for(int i=1;i<n;i++)
{

int j=i-1;

x=arr[i];

while(j>=0 && arr[j]>x)
{

arr[j+1]=arr[j];

j--;

}

arr[j+1]=x;

}

for(int i=0;i<n;i++)
{

cout<<arr[i]<<endl;
}

return 0;
}```
```output
2
3
6
8
12
56```

Here the time complexity is O(n*k).

### By using Heap data structure

Algorithm

1. Create a min-heap.
2. Then push first k elements of the array in heap.
3. Then pop elements and print them and add a new element.
4. Then pop the rest of the elements till the heap is empty.
```#include <iostream>
#include<queue>
using namespace std;

int main() {

int arr[6]={2,6,3,12,56,8};   //array declaring

int k=3;

int n=6;

priority_queue<int,vector<int>,greater<int> > q;  //declaring min heap

for(int i=0;i<k;i++)
{

q.push(arr[i]);                      //pushing first k elements

}

for(int i=k;i<n;i++)
{

cout<<q.top()<<" ";         //printing top of min heap

q.pop();          //pop element from min heap.

q.push(arr[i]);     //pushing rest of elements.

}

while(q.empty()==false)     //run loop while heap is not empty
{
cout<<q.top()<<" ";    //printing top of element of min heap.
q.pop();              //poping element.

}

return 0;
}```
```output
2
3
6
8
12
56```

Time complexity is  O(k) + O((n-k)*logk)