K-Messed Array Sort: Python Solution

K-Messed Array Sort

Given an array of integers arr where each element is at most k places away from its sorted position

Solution

from Queue import PriorityQueue


def sort_k_messed_array(arr, k):
  kheap = PriorityQueue()
  result = []
  
  for num in arr:
    kheap.put(num, 'num')
    
    if kheap.qsize() == (k + 1):
      item = kheap.get()
      result.append(item)
    
  while not kheap.empty():
    result.append(kheap.get())
    
  return result

arr = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9]
print(sort_k_messed_array(arr, 2))

Result

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Reference

• https://www.bogotobogo.com/python/python_PriorityQueue_heapq_Data_Structure.php