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
- Create a min-heap.
- Then push first k elements of the array in heap.
- Then pop elements and print them and add a new element.
- 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)
Leave a Reply