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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: