daily log 9.17.20

Priority Queues Mock

Given a k-sorted array that is almost sorted such that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

INPUT: Unsorted* Array OUTPUT: Sorted Array

Def sort_kids(kids, k): Sorted_kids = [] While i < len(kids) - k: K_kids = kids[i: k+1] my_magic_box = new MagicBox(k_kids) While len(my_magic_box) > 0: sorted_kids.append(my_magic_box.extract_min()) i+k

If I have 12 kids and k is 4 Take kids 1 - 4 Take kids 5 - 8 Take kids 9 - 12

If I have 12 kids and k is 4 Take kids 1 - 4 MB extract min Insert kid 5 MB extract min Insert kid 6 MB extract min Insert kid 7 … continue until kid_idx = len(array) -1 && MB.empty()