Compute the minimal number of swaps to order a sequence

by

I was able to prove this with graph-theory. Might want to add that tag in 🙂

Create a graph with n vertices. Create an edge from node n_i to n_j if the element in position i should be in position j in the correct ordering. You will now have a graph consisting of several non-intersecting cycles. I argue that the minimum number of swaps needed to order the graph correctly is

M = sum (c in cycles) size(c) - 1

Take a second to convince yourself of that…if two items are in a cycle, one swap can just take care of them. If three items are in a cycle, you can swap a pair to put one in the right spot, and a two-cycle remains, etc. If n items are in a cycle, you need n-1 swaps. (This is always true even if you don’t swap with immediate neighbors.)

Given that, you may now be able to see why your algorithm is optimal. If you do a swap and at least one item is in the right position, then it will always reduce the value of M by 1. For any cycle of length n, consider swapping an element into the correct spot, occupied by its neighbor. You now have a correctly ordered element, and a cycle of length n-1.

Since M is the minimum number of swaps, and your algorithm always reduces M by 1 for each swap, it must be optimal.

More Related Contents:

  1. C++ Sorting Algorithms [closed]
  2. Priority scoring algorithm [closed]
  3. Efficient way to add element to sorted datastructure [closed]
  4. How can I pair socks from a pile efficiently?
  5. What is stability in sorting algorithms and why is it important?
  6. Finding all cycles in a directed graph
  7. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  8. Find all paths between two graph nodes
  9. Is there an O(n) integer sorting algorithm?
  10. What’s the fastest algorithm for sorting a linked list?
  11. Find the shortest path in a graph which visits certain nodes
  12. Algorithm to separate items of the same type
  13. Optimal algorithm for returning top k values from an array of length N
  14. Find the paths between two given nodes?
  15. Fast algorithm implementation to sort very small list
  16. Sorting in linear time? [closed]
  17. How to rank a million images with a crowdsourced sort
  18. Sort Four Points in Clockwise Order
  19. Why is the time complexity of both DFS and BFS O( V + E )
  20. Quicksort vs heapsort
  21. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  22. Faster version of find for sorted vectors (MATLAB)
  23. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  24. Number of paths between two nodes in a DAG
  25. Can an array be grouped more efficiently than sorted?
  26. Search a sorted 2D matrix [duplicate]
  27. When is each sorting algorithm used? [closed]
  28. Why is bubble sort O(n^2)?
  29. Find the pair across 2 arrays with kth largest sum
  30. Find the k largest elements in order

Leave a Comment