Using a selection sort to sort an array in python. How can I optimize?

Question

Working on this challenge on HackerRank and got this code to pass 10 out of 15 test cases. It is failing due to timeout error which is HackerRank's way of telling you that the algorithm is not optimized. How can I optimize this code to run on larger input data?

The goal is to figure out the minimum number of swaps necessary to sort an unsorted array.

Update: Each element in the array is distinct.

def minimum_swaps(arr):
"""Returns the minimum number of swaps to re-oder array in ascending order."""

    swaps = 0
    for val in range(len(arr) - 1, 0, -1):

        # Index of max value
        max_pos = 0
        for index in range(1, val + 1):

            if arr[index] > arr[max_pos]:
                max_pos = index

        # Skip if value is already in sorted position
        if max_pos == val:
            continue

        arr[val], arr[max_pos] = arr[max_pos], arr[val]
        swaps += 1

    return swaps

user202729 · Accepted Answer · 2018-09-09 06:09:52Z

3

Look at the code. It has 2 nested loops:

The outer loop iterates over the positions val.
The inner loop finds the index of the value that should be at the index val, i.e., max_pos.

It takes a lot of time just to find the index. Instead, I will compute the index of each value and store it in a dict.

index_of = {value: index for index, value in enumerate(arr)}

(note that because all values in arr are distinct, there should be no duplicated keys)

And also prepare a sorted version of the array: that way it's easier to find the maximum value instead of having to loop over the array.

sorted_arr = sorted(arr)

Then do the rest similar to the original code: for each index visited, use sorted_arr to get the max, use index_of to get its current index, if it's out-of-place then swap. Remember to update the index_of dict while swapping too.

The algorithm takes O(n) operations (including dict indexing/modifying), plus sorting cost of n elements (which is about O(n log n)).

Note: If the array arr only contains integers in a small range, it may be faster to make index_of an array instead of a dict.

edited Sep 9, 2018 at 6:09

answered Sep 8, 2018 at 8:13

user202729

4,2293 gold badges31 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user202729 Over a year ago

There are other (similar) algorithms, but I choose to use the one that involves minimal modification to OP's code.

Martin Pekár · Accepted Answer · 2018-09-15 22:24:50Z

0

The short answer is: implement merge sort. The bubble sort algorithm you are using has a O(n^2) running time, while merge sort has a O(log_2(n)) running time.

answered Sep 15, 2018 at 22:24

Martin Pekár

293 bronze badges

Collectives™ on Stack Overflow

Using a selection sort to sort an array in python. How can I optimize?

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related