Search code examples
pythonsortingrefactoringselection-sort

How can I clean up this Selection Sort function in Python?

I just went through and converted a Selection Sort function written in C++ to Python.

I feel like I'm coding this too much like a C programmer, whereas I know Python has many in-built functions to use with for loops that would clean it up. I'm just not sure where to start.

What things could I change in this code to make it more idiomatic?

def selection_sort(A):
    for i in range(0, len(A) - 1):
        min_idx = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min_idx]:
                min_idx = j
        if min_idx != i:
            A[i], A[min_idx] = A[min_idx], A[i]

    return A
Solution

  • The code actually looks very pythonic already! Noteworthy, you swap values with the x, y = y, x idiom, this is highly encouraged in Python.

    Both Python2 and Python3:

    • range(0, x) is equivalent to range(x)
    • Optionally, you can lookup the minimum value index with A.index(min(A[i:])). This is largely dependent on taste and with very large lists it will be slower. IMHO looks nice and concise:
    def selection_sort(A):
    for i in range(0, len(A) - 1):
        min_idx = A.index(min(A[i:]))
        if min_idx != i:
            A[i], A[min_idx] = A[min_idx], A[i]

    return A

    Python2:

    • range makes a list - iterates over all elements - right away, xrange makes a lazy generator - iterates over the elements only when they're called for - it's preferred and often faster (it's not faster in the snippet you provided).

    General:

    • In a professional code review, you might be required to provide a docstring, roughly similar to:
    def selection_sort(A):
    """selection_sort performs an unstable in-place sort on A

    A -- list to be sorted.

    Returns A, sorted.
    """
    for i in range(0, len(A) - 1):
        min_idx = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min_idx]:
                min_idx = j
        if min_idx != i:
            A[i], A[min_idx] = A[min_idx], A[i]

    return A

    Sources: