Adjacent Swaps to Sort
Sequel to https://puzzlespree.substack.com/p/minimum-swaps-for-market-signal-sorting
Problem Statement
You are given an array of integers. You want to sort the array in ascending order using only swaps of adjacent elements. Determine the minimum number of such swaps required to accomplish this.
Examples
Example 1
Input: [4, 3, 1, 2, 5]
Output: 5
Explanation:
One valid sequence of adjacent swaps:
1) [4, 3, 1, 2, 5] → [3, 4, 1, 2, 5]
2) [3, 4, 1, 2, 5] → [3, 1, 4, 2, 5]
3) [3, 1, 4, 2, 5] → [1, 3, 4, 2, 5]
4) [1, 3, 4, 2, 5] → [1, 3, 2, 4, 5]
5) [1, 3, 2, 4, 5] → [1, 2, 3, 4, 5]
Total swaps = 5
Example 2
Input: [1, 5, 3, 2, 4]
Output: 4
Explanation:
One valid sequence:
1) Swap 5 and 3 → [1, 3, 5, 2, 4]
2) Swap 5 and 2 → [1, 3, 2, 5, 4]
3) Swap 5 and 4 → [1, 3, 2, 4, 5]
4) Swap 3 and 2 → [1, 2, 3, 4, 5]
Total swaps = 4Follow-up 1: Faster Algorithm
Can you design an algorithm that computes the minimum number of adjacent swaps in 𝑂(𝑛log𝑛) time?
Follow-up 2: Explicit Swap Sequence
Instead of just calculating the total swap count, how would you list every adjacent swap operation in order?
Really like this problem. It brings together a bunch of different ideas I previously learned.
I remember learning about inversions in my undergrad data structures class, which are pairs (i,j) of indices where array[i] > array[j], i.e. a larger element appears before a smaller element. For a sorted array, the number of inversions is 0. It turns out the minimum number of swaps needs is just the number of inversions in an array. This can be seen because each swap of adjacent elements decreases the number of inversions by at most one. In fact, this is exactly what insertion sort does; it swaps adjacent elements exactly K times, where K is the number of inversions.
To find the number of inversions, for each element, we need to count of elements to its left that are strictly greater than it. This is similar to a pretty popular leetcode problem. The way we do this in O(nlogn) time is through a variation of merge sort (divide & conquer):
1. Keep track of some kind of global counter for the number of inversions, K
2. Recursively divide the array until we get blocks of at most one element
3. In the merging phase, we merge two subarrays that were individually sorted from the previous level, updating K in the process. We assume that the inversions within individual subarrays have already been counted, so we just need to count the inversions between an element in the left array and an element in the right array. First, have two pointers, leftPtr and rightPtr for the left and right subarrays respectively. For each rightPtr value, we move leftPtr until the value at leftPtr > value at rightPtr or we reach the end of the left subarray. This gets us the number of elements in the left subarray that are greater than the rightPtr value, which we use to update K. Every time we move a pointer, we also add the value it pointed at to a new subarray, which stores the merged array. Once we reach the end of both subarrays, we return the merged array so the next level can use it.
This algorithm calculates the minimum number of swaps in O(nlogn) time and O(n) space.
To list the explicit swap sequence in order, we can just do insertion sort. Notice that the maximum number of inversions an array of N elements can have is N*(N-1) = O(N^2), which occurs when we have an array sorted in descending order. Thus insertion sort gives us the optimal algorithm, as we can just list the swap sequence in the order than insertion sort swaps adjacent elements.