You have a parking lot with parking spots numbered 1, 2, ..., n, to which n venture capitalists drive money-filled trucks of sizes a1, a2, ..., an (leaving no extra parking spaces).
You'd like to sort the trucks by size (so you can work your way down the list of trucks later talking with the venture capitalists about their terms), but you can only see along a limited distance of the parking lot at any one time, so (1) you can only compare the sizes of two trucks at most k parking spots away from each other1, and (2) you can only tell trucks at distance at most k from each other( That is, only trucks in spots i and j where |i - j| = k) to swap places.
a. Design an algorithm that compares two arbitrary trucks (not necessarily at distance at most k) in O(n/k) truck swaps (each of distance at most k), and returns any trucks that were moved in the process to their original positions.
b. Design an algorithm that switches two arbitrary trucks (not necessarily at distance at most k) in O(n/k) truck swaps (each of distance at most k), and returns any other trucks that were moved in the process to their original positions.
c. Describe an algorithm that sorts the trucks. You may possibly use the previous two parts