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. Following is the C code for standard Insertion Sort.
[pastacode lang=”c” manual=”%2F*%20Function%20to%20sort%20an%20array%20using%20insertion%20sort*%2F%0Avoid%20insertionSort(int%20A%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20int%20i%2C%20key%2C%20j%3B%0A%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%20size%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20key%20%3D%20A%5Bi%5D%3B%0A%20%20%20%20%20%20%20j%20%3D%20i-1%3B%0A%20%0A%20%20%20%20%20%20%20%2F*%20Move%20elements%20of%20A%5B0..i-1%5D%2C%20that%20are%20greater%20than%20key%2C%20to%20one%20%0A%20%20%20%20%20%20%20%20%20%20position%20ahead%20of%20their%20current%20position.%0A%20%20%20%20%20%20%20%20%20%20This%20loop%20will%20run%20at%20most%20k%20times%20*%2F%0A%20%20%20%20%20%20%20while%20(j%20%3E%3D%200%20%26%26%20A%5Bj%5D%20%3E%20key)%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20A%5Bj%2B1%5D%20%3D%20A%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20j-1%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20A%5Bj%2B1%5D%20%3D%20key%3B%0A%20%20%20%7D%0A%7D” message=”c” highlight=”” provider=”manual”/]
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)
[ad type=”banner”]We can sort such arrays more efficiently with the help of Heap data structure. Following is the detailed process that uses Heap.
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)
[pastacode lang=”c” manual=”%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Prototype%20of%20a%20utility%20function%20to%20swap%20two%20integers%0Avoid%20swap(int%20*x%2C%20int%20*y)%3B%0A%20%0A%2F%2F%20A%20class%20for%20Min%20Heap%0Aclass%20MinHeap%0A%7B%0A%20%20%20%20int%20*harr%3B%20%2F%2F%20pointer%20to%20array%20of%20elements%20in%20heap%0A%20%20%20%20int%20heap_size%3B%20%2F%2F%20size%20of%20min%20heap%0Apublic%3A%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20MinHeap(int%20a%5B%5D%2C%20int%20size)%3B%0A%20%0A%20%20%20%20%2F%2F%20to%20heapify%20a%20subtree%20with%20root%20at%20given%20index%0A%20%20%20%20void%20MinHeapify(int%20)%3B%0A%20%0A%20%20%20%20%2F%2F%20to%20get%20index%20of%20left%20child%20of%20node%20at%20index%20i%0A%20%20%20%20int%20left(int%20i)%20%7B%20return%20(2*i%20%2B%201)%3B%20%7D%0A%20%0A%20%20%20%20%2F%2F%20to%20get%20index%20of%20right%20child%20of%20node%20at%20index%20i%0A%20%20%20%20int%20right(int%20i)%20%7B%20return%20(2*i%20%2B%202)%3B%20%7D%0A%20%0A%20%20%20%20%2F%2F%20to%20remove%20min%20(or%20root)%2C%20add%20a%20new%20value%20x%2C%20and%20return%20old%20root%0A%20%20%20%20int%20replaceMin(int%20x)%3B%0A%20%0A%20%20%20%20%2F%2F%20to%20extract%20the%20root%20which%20is%20the%20minimum%20element%0A%20%20%20%20int%20extractMin()%3B%0A%7D%3B%0A%20%0A%2F%2F%20Given%20an%20array%20of%20size%20n%2C%20where%20every%20element%20is%20k%20away%20from%20its%20target%0A%2F%2F%20position%2C%20sorts%20the%20array%20in%20O(nLogk)%20time.%0Aint%20sortK(int%20arr%5B%5D%2C%20int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20Min%20Heap%20of%20first%20(k%2B1)%20elements%20from%0A%20%20%20%20%2F%2F%20input%20array%0A%20%20%20%20int%20*harr%20%3D%20new%20int%5Bk%2B1%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%3C%3Dk%20%26%26%20i%3Cn%3B%20i%2B%2B)%20%2F%2F%20i%20%3C%20n%20condition%20is%20needed%20when%20k%20%3E%20n%0A%20%20%20%20%20%20%20%20harr%5Bi%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20MinHeap%20hp(harr%2C%20k%2B1)%3B%0A%20%0A%20%20%20%20%2F%2F%20i%20is%20index%20for%20remaining%20elements%20in%20arr%5B%5D%20and%20ti%0A%20%20%20%20%2F%2F%20is%20target%20index%20of%20for%20cuurent%20minimum%20element%20in%0A%20%20%20%20%2F%2F%20Min%20Heapm%20’hp’.%0A%20%20%20%20for(int%20i%20%3D%20k%2B1%2C%20ti%20%3D%200%3B%20ti%20%3C%20n%3B%20i%2B%2B%2C%20ti%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20are%20remaining%20elements%2C%20then%20place%0A%20%20%20%20%20%20%20%20%2F%2F%20root%20of%20heap%20at%20target%20index%20and%20add%20arr%5Bi%5D%0A%20%20%20%20%20%20%20%20%2F%2F%20to%20Min%20Heap%0A%20%20%20%20%20%20%20%20if%20(i%20%3C%20n)%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bti%5D%20%3D%20hp.replaceMin(arr%5Bi%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Otherwise%20place%20root%20at%20its%20target%20index%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20reduce%20heap%20size%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bti%5D%20%3D%20hp.extractMin()%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20FOLLOWING%20ARE%20IMPLEMENTATIONS%20OF%20STANDARD%20MIN%20HEAP%20METHODS%20FROM%20CORMEN%20BOOK%0A%2F%2F%20Constructor%3A%20Builds%20a%20heap%20from%20a%20given%20array%20a%5B%5D%20of%20given%20size%0AMinHeap%3A%3AMinHeap(int%20a%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%20heap_size%20%3D%20size%3B%0A%20%20%20%20harr%20%3D%20a%3B%20%20%2F%2F%20store%20address%20of%20array%0A%20%20%20%20int%20i%20%3D%20(heap_size%20-%201)%2F2%3B%0A%20%20%20%20while%20(i%20%3E%3D%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20MinHeapify(i)%3B%0A%20%20%20%20%20%20%20%20i–%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Method%20to%20remove%20minimum%20element%20(or%20root)%20from%20min%20heap%0Aint%20MinHeap%3A%3AextractMin()%0A%7B%0A%20%20%20%20int%20root%20%3D%20harr%5B0%5D%3B%0A%20%20%20%20if%20(heap_size%20%3E%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20harr%5B0%5D%20%3D%20harr%5Bheap_size-1%5D%3B%0A%20%20%20%20%20%20%20%20heap_size–%3B%0A%20%20%20%20%20%20%20%20MinHeapify(0)%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F%2F%20Method%20to%20change%20root%20with%20given%20value%20x%2C%20and%20return%20the%20old%20root%0Aint%20MinHeap%3A%3AreplaceMin(int%20x)%0A%7B%0A%20%20%20%20int%20root%20%3D%20harr%5B0%5D%3B%0A%20%20%20%20harr%5B0%5D%20%3D%20x%3B%0A%20%20%20%20if%20(root%20%3C%20x)%0A%20%20%20%20%20%20%20%20MinHeapify(0)%3B%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20method%20to%20heapify%20a%20subtree%20with%20root%20at%20given%20index%0A%2F%2F%20This%20method%20assumes%20that%20the%20subtrees%20are%20already%20heapified%0Avoid%20MinHeap%3A%3AMinHeapify(int%20i)%0A%7B%0A%20%20%20%20int%20l%20%3D%20left(i)%3B%0A%20%20%20%20int%20r%20%3D%20right(i)%3B%0A%20%20%20%20int%20smallest%20%3D%20i%3B%0A%20%20%20%20if%20(l%20%3C%20heap_size%20%26%26%20harr%5Bl%5D%20%3C%20harr%5Bi%5D)%0A%20%20%20%20%20%20%20%20smallest%20%3D%20l%3B%0A%20%20%20%20if%20(r%20%3C%20heap_size%20%26%26%20harr%5Br%5D%20%3C%20harr%5Bsmallest%5D)%0A%20%20%20%20%20%20%20%20smallest%20%3D%20r%3B%0A%20%20%20%20if%20(smallest%20!%3D%20i)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20swap(%26harr%5Bi%5D%2C%20%26harr%5Bsmallest%5D)%3B%0A%20%20%20%20%20%20%20%20MinHeapify(smallest)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20swap%20two%20elements%0Avoid%20swap(int%20*x%2C%20int%20*y)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*x%3B%0A%20%20%20%20*x%20%3D%20*y%3B%0A%20%20%20%20*y%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20array%20elements%0Avoid%20printArray(int%20arr%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20for%20(int%20i%3D0%3B%20i%20%3C%20size%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%20%20%20cout%20%3C%3C%20endl%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20k%20%3D%203%3B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B2%2C%206%2C%203%2C%2012%2C%2056%2C%208%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20sortK(arr%2C%20n%2C%20k)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Following%20is%20sorted%20array%5Cn%22%3B%0A%20%20%20%20printArray%20(arr%2C%20n)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]Output:
Following is sorted array 2 3 6 8 12 56
The Min Heap based method takes O(nLogk) time and uses O(k) auxiliary space.
We can also use a Balanced Binary Search Tree instead of Heap to store K+1 elements. The insert and delete operations on Balanced BST also take O(Logk) time. So Balanced BST based method will also take O(nLogk) time, but the Heap bassed method seems to be more efficient as the minimum element will always be at root. Also, Heap doesn’t need extra space for left and right pointers.
Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.
[ad type=”banner”]