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.

user_6726632 · Answer

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.

Sorting Algorithm for expensive swapping?

1 Answers