Sorting of partially or k sorted array in C++

By Ayush Tripathi

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)