Massive Algorithms: Sort a nearly sorted (or K sorted) array

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 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.

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();

}

}

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)

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

Sort a nearly sorted (or K sorted) array | GeeksforGeeks

Labels

Popular Posts