madver's blog

Minimum number of swaps required to sort an array
By madver, history, 6 years ago, In English

Hello everybody. Today, i hope you can help me to solve this problem. I have many ways to solve it if the array has distinct integers. But if the array has repeated elements, i think it is very hard. Can anyone give me some advice ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Haven't put much thought on this, but my guess would be n - k, where n is the size of the array and k is the value of longest not decreasing subsequence.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    for test

    2 3 4 ... n 1

    you would return 1 instead of n — 1

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sure! Got it wrong. I think the problem it solves is when you are able to change the position of a element instead of swapping two. Any counter examples for this problem?

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If you have several equal elements you will never make a swap between them, so you can replace each element with the tuple (ai, i). Notice that now all elements are distinct (and solving this problem is equivalent to solve the previous) and you can do whatever algo you know to solve this.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would it work for the sequence 1 3 2 2?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Of course. You need to sort the array: [(1, 1);(3, 2);(2, 3);(2, 4)]

      The sorted version will be: [(1, 1);(2, 3);(2, 4);(3, 2)]

      Notice when comparing tuple we first compare first element, and in case they differ we compare the second element.

      In this case you only need two swaps. Actually, after you replace each element by a tuple, you can replace each element by a different integer in the range [1, n], assigning each element its final position in the array, and now you need to solve the problem in a permutation. (Notice you need to sort the array first, to find it's final position).

      In this case (1,1) -> 1 (2,3) -> 2 (2,4) -> 3 (3,2) -> 4

      so the array you need to sort is:

      (1, 4, 2, 3)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        But you may use one swap only: between the 3 and the last 2.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          My bad, I was thinking in the problem:

          Performing swaps between adjacents elements

          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Will this work if we allow to swap not only adjacent elements?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Friend of mine was asked the same question in Zalando interview round. Could not solve this too. Swapping any two elements is allowed. Anyone with a solution?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think you or your friend lied. Because there is currently a problem like this in USACO bronze

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I have an idea based on the idea of finding "cycles" (kind of like in IOI 1996 "Sorting a Three-Valued Sequence"):

We sort the array, and make notes of where the original array and the sorted array are different. Then, we go from left to right, and whenever we find an index such that the two arrays differ, we do this process:

-in the original array, swap the element at the current index with the element that is at an index where it could be if the array were sorted (for example, if the max element is not where it should be, we would possibly swap it with the element located at the last index). Make sure that while making this swap the two elements have different values (so that it's not a useless swap).

-keep on continuing this process until an element that actually belongs at the current index is swapped in.

→ Reply