Restore original array after selection sort using swap distances

Question

I am new in CS, and I have a really hard task to do. This t h i n g scares me. During selection sort we can acquire swap distances -- difference between (index value of element in unsorted array) and (index value of element in sorted array). We can find it for example like this (here is the sum of swap distances(code written by myself, calculating sum of swap distances was my previous task), but we can easily obtain a list of swap distances):

x = [int(i) for i in input().split()]
def sel_sort(a):
    swap_dist_sum = 0 
    for i in range(len(a)): 
        min_idx = i 
        for j in range(i+1, len(a)): 
            if a[min_idx] > a[j]: 
                min_idx = j       
        a[i], a[min_idx] = a[min_idx], a[i]
        swap_dist_sum += (min_idx - i)  # new index in sorted list - index from unsorted list
    return swap_dist_sum                # for each element
print(sel_sort(x))

This was only the intro(this definition is rare). I have (n - 1) numbers which are swap distances; 1st element from 1st sort iteration, 2nd from 2nd and so on. I have to restore original order of elements in unsorted array of n elements. I have no idea what I should do. Maybe you can advice me to find/read/use library/little code hints/etc.

Sample Input:  # swap distances
1 3 0 1

Sample Output:  # original list
4 1 3 5 2

My first steps should be like this:

swap_dist_l = [int(i) for i in input().split()]  # list containing all swap distances
sorted_l = [i for i in range(1, len(swap_dist_l) + 2)]  # already sorted list

As a result, I should have unsorted_l with original unsorted order of elements. Sorry if my speech is hard to understand! P.S. I didn't find any similar/duplicate questions. Pls send a link if I'm bad at searching!

Answer 1

You should perform the swaps that correspond to the swap distances you get, but in reversed order, so starting from the right:

def unsort(data_l, swap_dist_l):
    for i, dist in reversed(list(enumerate(swap_dist_l))):
        # swap
        data_l[i+dist], data_l[i] = data_l[i], data_l[i+dist]

Call as follows for the example given:

swap_dist_l = [1, 3, 0, 1]
data_l = [i for i in range(1, len(swap_dist_l) + 2)]  # [1, 2, 3, 4, 5] 
unsort(data_l, swap_dist_l)
print(data_l)  # [4, 1, 3, 5, 2]