Array sorting timing out for huge size of arrays

user_971741 0
Viewed 65

I am doing on online code challenge. I have array which I need to sort and record to minimum number of iterations required to be sorted. I have the following code.

def minSwap(ar):
    c = 0

    for i in range(0, len(ar)):
        if ar[i] == i+1:
            continue
        else:
            for k in range(i+1, len(ar)):
                if ar[k] == i+1:
                    ar[k] = ar[i]
                    ar[i] = i+1
                    c = c+1
                    break
    return c

This code passes majority of test cases, however for really huge number of case such as where array size is beyond lets say 50000 it gets timeout.

Can anyone help identify the faulty block of code that I am doing incorrect, I cant see a way to tweak it further?

python-3.x algorithm
3 Answers

From your code I take it that sorting isn't the issue here, since you know you'll end up with ar[i] == i+1. Given that, why not change your else block to swap the current element into its slot, and repeat until you ar[i] is correct.

    else:
        while ar[i] != i+1:
            temp = ar[i]
            ar[i] = ar[temp - 1]
            ar[temp - 1] = temp
user_20410770

You don't actually need to do a sort on this array. You just need to figure out the minimum number of swaps needed. If we just look at the following pattern, we can form a hypothesis to be tested:

  • 1234 = 0
  • 1324 = 1, swap 2 and 3
  • 1423 = 2, swap 2 and 4, swap 3 and 4
  • 4213 = 2, swap 1 and 4, swap 3 and 4
  • 4123 = 3, swap 4 and 1, swap 4 and 2, swap 4 and 3

Based on these observations, I think we can work on the hypothesis that the answer will be max(0, n - 1) where n is the count of the number of "out of place" elements.

Then the code becomes simplified to:

def minSwap(ar):
    c = 0

    for i in range(0, len(ar)):
        if ar[i] != i+1:
            c = c + 1
    return c < 0 ? 0 : c

Note that I don't actually know python so don't know if that last ternary is valid in python.

user_26467720

Looking at the problem statement, it looks like you want to sort a list that has numbers starting from 1 thru n.

If you are trying to sort the list, and the final list is expected to be [1, 2, 3, 4, 5, 6, 7 , 8, .....], then all you need to do is to insert the i+1 to the current position and pop the value of i+1 from its current position. That will reduce the number of iterations you need to sort or swap.

Here's the code that does this with least number of moves. At least that's what I found based on my tests.

def minSwap(ar):
    c=0
    for i in range(0, len(ar)):
        if ar[i] != i+1:

            #find the value of i+1 from i+1th position
            temp = ar.index(i+1,i+1) 
            
            ar.insert(i,i+1) #insert i+1 in the ith position

            ar.pop(temp+1) #remove the value of i+1 from the right

            c+=1 #every time you do a swap, increment the counter
    print (ar) #if you want to check if ar is correct, use this print stmt
    return c

a = [1,3,4,5,6,7,2,8]

print (minSwap(a))

The total number of swaps for the above example is 1. It just inserts 2 in the second place and pops out 2 from position 6.

I ran the code for a = [1,6,5,4,3,8,2,7] and it swapped in 5 moves.

I ran the code for a = [1,3,5,4,6,8,2,7] and it swapped in 3 moves.

If you are trying to figure out how this works, use a print statement right after the if statement. It will tell you the element being swapped.

user_138739800
Related