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.
We can use Insertion Sort to sort the elements efficiently.
The inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)
http://elise.co.nf/?p=957
实际上不用新建返回数组,可直接修改原数组
Palantir面经
Sort the nearly sorted array, in the array, every element is at most k distance with its final place. 一开始用常规的k size heap,但是被明确要求用multi-thread来提速,这个方法是不行了。应该用2K的方法来divide and conquer。用多线程最终可以提速到O(klogk)
first, mention insertion sort, O(nk) inner loop只需要比较k次
second, heap O(nlogk) 前面k个还可以有heapify做
third, divide into n/k份, 依次merge B_i B_(i+1), 那么B_i sorted, B_i+1 ksorted,
http://bylijinnan.iteye.com/blog/1752041
Read full article from Sort a nearly sorted (or K sorted) array | GeeksforGeeks
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.
We can sort such arrays more efficiently with the help of Heap data structure.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logK)
int
sortK(
int
arr[],
int
n,
int
k)
{
// Create a Min Heap of first (k+1) elements from
// input array
int
*harr =
new
int
[k+1];
for
(
int
i = 0; i<=k && i<n; i++)
// i < n condition is needed when k > n
harr[i] = arr[i];
MinHeap hp(harr, k+1);
// i is index for remaining elements in arr[] and ti
// is target index of for cuurent minimum element in
// Min Heapm 'hp'.
for
(
int
i = k+1, ti = 0; ti < n; i++, ti++)
{
// If there are remaining elements, then place
// root of heap at target index and add arr[i]
// to Min Heap
if
(i < n)
arr[ti] = hp.replaceMin(arr[i]);
// Otherwise place root at its target index and
// reduce heap size
else
arr[ti] = hp.extractMin();
}
}
The inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)
void
insertionSort(
int
A[],
int
size)
{
int
i, key, j;
for
(i = 1; i < size; i++)
{
key = A[i];
j = i-1;
/* Move elements of A[0..i-1], that are greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while
(j >= 0 && A[j] > key)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = key;
}
}
http://elise.co.nf/?p=957
实际上不用新建返回数组,可直接修改原数组
public void sort(int[] input, int k) { if(input.length==0 || input==null) return; PriorityQueue<Integer> pq = new PriorityQueue<>(); int i = 0; for(;i<k+1;i++) pq.offer(input[i]); int index = 0; while(!pq.isEmpty()) { input[index] = pq.poll(); if(i<input.length) pq.offer(input[i]); index++; i++; } }http://lhearen.top/2016/10/16/K-distance-Sort/
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).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++]);}}
Palantir面经
Sort the nearly sorted array, in the array, every element is at most k distance with its final place. 一开始用常规的k size heap,但是被明确要求用multi-thread来提速,这个方法是不行了。应该用2K的方法来divide and conquer。用多线程最终可以提速到O(klogk)
first, mention insertion sort, O(nk) inner loop只需要比较k次
second, heap O(nlogk) 前面k个还可以有heapify做
third, divide into n/k份, 依次merge B_i B_(i+1), 那么B_i sorted, B_i+1 ksorted,
http://bylijinnan.iteye.com/blog/1752041
Read full article from Sort a nearly sorted (or K sorted) array | GeeksforGeeks