K-distance Sort

K-Distance Sort

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.

For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.

test

Solution

Actually we can easily utilize Insertion Sort to sort it in O(nk) but it’s not ideal. Let’s try to use a small minHeap (of size k+1) to optimize it to O(nlogk).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void sortKDistance(vector<int>& arr, int k){
priority_queue<int, vector<int>, greater<int>> minHeap(arr.begin(), arr.begin()+k+1);
int i = k+1, j = 0;
while(j < arr.size()){
arr[j++] = minHeap.top();
minHeap.pop();
if(i < arr.size()) minHeap.push(arr[i++]);
}
}
int main(int argc, char *argv[])
{
vector<int> arr{2, 6, 3, 12, 56, 8};
sortKDistance(arr, 2);
for(auto n: arr) cout<<n<<",";
cout<<endl;
return 0;
}

Always welcome new ideas and practical tricks, just leave them in the comments!