Sorting Algorithm for expensive swapping?

Question

I came across the following problem in the application I'm developing:

I'm given two lists:

list1 = { Z, K, A, B, A, C }

list2 = { A, A, B, C, K, Z }

list2 is the guaranteed to be the sorted version of list1.

My objective is to sort list1 only by swapping elements within list1. So for example, I cannot iterate through list2 and simply assign every element i in list1 to every element j in list2.

Using list2 as a resource, I need to sort list1 in the absolute minimum number of swaps possible.

Is there a set of algorithms specifically for this purpose? I've not heard of such a thing.

@WillemVanOnsem That would be `O(n!)` is that correct? For every index of `list1`, you need to perform a linear search for the element that should go in that index? Is there anything better than this? — Hatefiend, Nov 06 '18 at 14:35
no, in searching it is *O(n^2)*, but if we can make extra datastructures, etc. than even that can be minimized. For every item, we perform a "linear search" on the tail. — Willem Van Onsem, Nov 06 '18 at 14:37
Sorting with minimum swaps is not a particularly rare problem - [Compute the minimal number of swaps to order a sequence](https://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence) (but that's for distinct elements) — Bernhard Barker, Nov 06 '18 at 14:37
Using the example above, start at index `0`, element that belongs here is `A`, linear search `list1` for `A`, which returns index `2`. Swap index `0` with `2`, etc. — Hatefiend, Nov 06 '18 at 14:38
Exactly, but that is not *O(n!)*, since as a result we know that *both* the element we swapped from and to are now correct. We advance the cursor. Each iteration takes linear time in searching, and constant time in swapping, and we thus can each time advance the cursor, so *O(n^2)*. — Willem Van Onsem, Nov 06 '18 at 14:39
"in the application [you're] developing"? Are you sure this isn't homework or a question from a programming contest? In the real world you're not going to care about the absolute minimum number of swaps in 99.9999% of cases, and you'll probably just run a normal sort based on the indices in the second list. — Bernhard Barker, Nov 06 '18 at 14:41
@Dukeling In the application I am working with, every swap requires contacting a server and getting permission to switch the elements. It's very expensive. Performing mergesort or some O(n logn) swaps algorithm is too much strain. — Hatefiend, Nov 06 '18 at 14:45
@Hatefiend Then you might have [an XY problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) on your hands. — Bernhard Barker, Nov 06 '18 at 14:52
You should elaborate on what you mean by saying that a swap requires contacting a server to get permission. Because if your problem is that at some point you might get a "permission denied" or something, you're probably better off copying the sorted one over your original list, send that to the server and see if it's accepted. If that doesn't comply with your requirements, then @Dukeling is right and you have an XY problem. — ChatterOne, Nov 06 '18 at 15:06
@ChatterOne I'm familiar with the XY problem and trust me it's not relevant here. I was trying to explain why swapping elements is so expensive. Every swap involves multiple HTTP requests, etc. This is why I need to have the absolute minimum swaps. O(n^2) though is not ideal. I was hoping there would be a faster solution. — Hatefiend, Nov 06 '18 at 15:17
@Hatefiend My question was more like: why can't you just send `list2` or even a clone of it directly and see if that's accepted from the server? — ChatterOne, Nov 06 '18 at 15:29
@ChatterOne I see. In my question I gave the restriction `My objective is to sort list1 only by swapping elements within list1`. The application I am working with only allows me to read elements or swap elements. I cannot provide it with a list of elements and have it mutate the list. — Hatefiend, Nov 06 '18 at 15:32
@Hatefiend Ok. Then another question: do you have a limited set of elements? Specifically: could you reduce the problem to having two strings and calculating the levenshtein distance? — ChatterOne, Nov 06 '18 at 15:42
Possible duplicate of [Finding the minimum number of swaps to convert one string to another, where the strings may have repeated characters](https://stackoverflow.com/questions/18292202/finding-the-minimum-number-of-swaps-to-convert-one-string-to-another-where-the) — juvian, Nov 06 '18 at 20:47
@ChatterOne I'm assuming the levenshtein distance would calculate how many swaps I would need? Unfortunately I would need to actually know which elements to swap and in what sequence, not just how many swaps total I will need. I don't have a limited set of elements however. This is interesting though, thank you for linking it. — Hatefiend, Nov 06 '18 at 23:27

Ahmad Shabib · Answer 1 · 2018-11-08T06:44:21.583

I wrote this code in java in order to do the minimal swaps, Since the second list is guaranteed to be sorted we can look up for each element in it and find its index from the first list then do a swap between the current indexed element and the one that we found.

Update: I modified findLastElementIndex as it checks if the swapped element will be in the right index after swapping based on list2.

public class Testing {

    private static String[] unorderedList = {"Z", "C", "A", "B", "A", "K"};
    private static String[] orderedList = {"A", "A", "B", "C", "K", "Z"};
    private static int numberOfSwaps;

    public static void main(String[] args) {
        for (int i = 0; i < unorderedList.length; i++) {
            if (!unorderedList[i].equals(orderedList[i])) {
                int index = findElementToSwapIndex(i, orderedList[i]);
                swapElements(unorderedList, i, index);
            }
        }
        System.out.println(numberOfSwaps);
    }

    private static void swapElements(String[] list, int indexOfFirstElement, int IndexOfSecElement) {
        String temp = list[indexOfFirstElement];
        list[indexOfFirstElement] = list[IndexOfSecElement];
        list[IndexOfSecElement] = temp;
        numberOfSwaps++;
    }

    private static int findElementToSwapIndex(int currentIndexOfUnorderedList , String letter) {
        int lastElementToSwapIndex = 0;
        for (int i = 0; i < unorderedList.length; i++) {
            if (unorderedList[i].equals(letter)) {
                lastElementToSwapIndex = i;
            if(unorderedList[currentIndexOfUnorderedList].equals(orderedList[lastElementToSwapIndex])){// check if the swapped element will be in the right place in regard to list 2
                    return lastElementToSwapIndex;
                }
            }
        }
        return lastElementToSwapIndex;
    }
}

min number of swaps for this code was the same as in https://stackoverflow.com/a/40507589/6726632

Hopefully this can help you.

This will return 3 instead of 2 for `list1 = {"D", "E", "C", "C"}, list2 = {"C", "C", "D", "E"};`. The linked post is different because in that case only unique elements are allowed. — Bernhard Barker, Nov 06 '18 at 15:35
you are right, In my case i choose to get the last appearance of the letter if it was not unique for this approach it might and might not get the absolute minimal cause it depends on which one you are swapping. — Ahmad Shabib, Nov 06 '18 at 16:53
@Dukeling Are you aware of a way to do this with duplicates? — Hatefiend, Nov 07 '18 at 08:21

Sorting Algorithm for expensive swapping?

1 Answers1