Home

Minimum Swaps

How to

Given array [7, 1, 3, 2, 4, 5, 6], what are the minimum swaps to sort this algorithm?

Notes

  1. We want this to be efficient, so selection sort doesn't cut it.

Solution

  1. Build an array of indexes for where the next indexOf for the element you want is.
  2. For i = 0..n-1, if arr[0] !== i + 1, then swap arr[i] with arr[indexes[i]].
  3. Finally, swap indexes[arr[i] = 1] with the new position indexes[i].
  4. Increment swaps.
  5. Continue.

This solution will have a run time of n.

// Complete the minimumSwaps function below. function minimumSwaps(arr) { let swaps = 0; // Build an array of indexes for where the next `indexOf` for the element you want is. const indexes = arr.map((_, i) => arr.indexOf(i + 1)); for (let i = 0; i < arr.length; i++) { // if !== 1 if (arr[i] !== i + 1) { // 7 const temp = arr[i]; // set arr[1] to 1 arr[i] = arr[indexes[i]]; // set arr[1] to 7 arr[indexes[i]] = temp; // set indexes[6] to indexes[temp - 1] = indexes[i]; // increment swaps swaps++; } } return swaps; }