How to Sort a nearly sorted (or K sorted) array in Python
In this tutorial, we’ll learn how to sort a nearly sorted array (or K sorted array) in Python.
K sorted array means that every element is at most K steps ahead or behind it’s sorted index.
Consider an array = [3,1,2,4] and K=2
The sorted array would be [1,2,3,4]. We can see that every element is at most 2 steps away from its actual position in the sorted array.
- The idea is to make use of the heap data structure.
- Take first k elements in another array and heapify them. This will create a min-heap of first k elements.
- Then run a loop for the remaining elements and keep on popping and pushing elements into the heap. Each element popped is stored in the original array at its proper location using another variable.
- When the above loop terminates and length of the heap is not 0, then run a loop till elements in heap is 0, pop elements from the heap and store it in the original array.
- After the above loop terminates print the original array elements.
Implementation: Sort a nearly sorted (or K sorted) array in Python
The code for the above approach is as follows :
from heapq import heapify,heappush,heappop def sort(l,n,k): heap=l[:k+1] heapify(heap) j=0 for i in range(k+1,n): l[j]=heappop(heap) heappush(heap,l[i]) j+=1 while len(heap)!=0: l[j]=heappop(heap) j+=1 print(*l) k=2 l=[5,3,2,8,7,6] sort(l,len(l),k)
Output : 2 3 5 6 7 8
Recommended Posts :