0

I am trying to calculate the number of minimum swaps while sorting an unordered array with integers.

An example.

Input;

array = [4, 3, 1, 2]
calculate_swaps(array)

Output;

# Initial array = [4, 3, 1, 2]
# 1st iteration = [1, 3, 4, 2]
# 2nd iteration = [1, 2, 4, 3]
# 3rd iteration = [1, 2, 3, 4]

3 # minimum amount of swaps to sort the array.

I have tried "selection sorting algorithm' here below. It works. Since it performs with O(n2) time complexity, my algorithm takes too much time for calculation on big arrays (with size = 50,000).

Here is my code. How can I overcome this performance issue?

def calculate_swaps(arr):
    min_swaps = 0
    minimum = 0
    for i in range(len(arr) - 1):
        if (arr[i] == i + 1):
            continue

        minimum = i

        for j in range(i + 1, len(arr)):
            # Find the smallest value
            if arr[j] < arr[minimum]:
                minimum = j

        # Swap
        if minimum != i:
            arr[minimum], arr[i] = arr[i], arr[minimum]
            min_swaps += 1

    return(min_swaps)
Enis Arik
  • 665
  • 10
  • 24
  • 2
    Honestly, you should just use the built in array sorting methods. You are highly unlikely to get better performance creating your own. Unlike anything you will likely come up with on your own, they have been optimized over decades and scrutinized by many people contributing to the python project. – Axe319 Apr 13 '20 at 13:31
  • 1
    You can read the documentation for the builtin `sort()` and `sorted` here. http://svn.python.org/projects/python/trunk/Objects/listsort.txt – Axe319 Apr 13 '20 at 13:40
  • I actually want to calculate number of swaps during sorting. Thats why I need a hand-made function for this. I am not sure if builtin functions will work. I modified my question accordingly. – Enis Arik Apr 13 '20 at 13:44
  • 1
    Find the cycle structure of the permutation whose inverse you are implicitly finding with the sort. Once you have that, everything is easy. – John Coleman Apr 13 '20 at 14:19

0 Answers0