CODEWITHSUNDEEP
pythonarraysalgorithmsortingselection-sort
Ignat Sonets
Ignat Sonets

Reputation: 43

Restore original array after selection sort using swap distances

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!

Upvotes: 1

Views: 419

Answers (2)

trincot
trincot

Reputation: 350766

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]

Upvotes: 1

Martin Gustafsson
Martin Gustafsson

Reputation: 303

Lets look at how selection sort works for a simple list lst = [3,1,2]:

We first look at index 0 and find the smallest element which is 1 at index 1.

We then swap these, i.e. lst[0], lst[1] = lst[1], lst[0]

Then we look at index 1 and find the smallest element which is 2 at index 2.

We then swap these, i.e. lst[1], lst[2] = lst[2], lst[1]

Now the list is sorted and we have a list of swap distances swap_dst = [1,1]

In order to restore the list we then need to reverse the swaps we did to get it sorted or in other words we need to do the same swaps again but in reversed order.

lst = [1,2,3]
lst[1], lst[2] = lst[2], lst[1]
lst[0], lst[1] = lst[1], lst[0]
print(lst) # [3,1,2]

So what you need to do is find out how to use the swap distances to find what swaps were made and do those swaps again.

Upvotes: 0

Related Questions