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.

Illustration :

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.

Approach :

• 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 :

Binary heap implementation in Python

How to Implement Heap Sort using Java