Selection Sort Algorithm (Python)

Question

Selection Sort

The selection sort algorithm sorts a list by finding the minimum element from the right unsorted part of the list and putting it at the left sorted part of the list. The algorithm maintains two sub-lists in a given input list.

1) The sub-list which is already sorted.
2) Remaining sub-list which is unsorted.

In every iteration of selection sort, the minimum element from the unsorted sub-list is picked and moved to the sorted sub-list.

I've been trying to implement the Selection Sort algorithm using Python magic functions such as __iter__ and I'd appreciate it if you'd review the code for changes/improvements.

Code

""" This class returns an ascending sorted integer list for an input integer list using Selection Sort method. Sorting: - In-Place (space complexity O(1)) - Efficiency (time complexity O(N^2)) - Unstable Sort (Order of equal elements might change) """ class SelectionSort(object): """ """ def __init__(self, input_list:list)->list: self.input_list = input_list self.__iter__() def __iter__(self)->list: """ Iterates through the list and swaps the min from the right side to sorted elements from the left side of the list. """ # Is the length of the list input_length = len(self.input_list) # Iterates through the list to do the swapping for element_index in range(input_length - 1): min_index = element_index # Iterates through the list to find the min index for finder_index in range(element_index+1, input_length): if self.input_list[min_index] > self.input_list[finder_index]: min_index = finder_index # Swaps the min value with the pointer value if element_index is not min_index: self.input_list[element_index], self.input_list[min_index] = self.input_list[min_index], self.input_list[element_index] print(self.input_list) return self.input_list SelectionSort([10, 4, 82, 9, 23, -30, -45, -93, 23, 23, 23, 0, -1]) 

Solution from Geeks by Geeks

I'm not so sure about Sorting Stability, it says the following implementation is not stable. However, Selection Sort can be made stable:

import sys A = [64, 25, 12, 22, 11] for i in range(len(A)): min_index = i for j in range(i+1, len(A)): if A[min_index] > A[j]: min_index = j A[i], A[min_index] = A[min_index], A[i] for i in range(len(A)): print("%d" %A[i]) 

Reference

• Selection Sort (Geeks for Geeks)
• Selection Sort (Wiki)

Answer 1

I agree with @Reinderien that this shouldn't be a class. You can see evidence for this in your constructor:

def __init__(self, input_list:list)->list: self.input_list = input_list self.__iter__() 

You are constructing the object (and calling the constructor) simply to call self.__iter__(). There is no reason for the creation of an object here just to sort the list. If you needed to maintain some state between sorts or something (I'm not sure why you would though), then it may be appropriate.

I'll also point out, you're attempting to violate at least two "contracts" with your usage of __init__ and __iter__:

• __init__ must return None:

  no non-None value may be returned by __init__(); doing so will cause a TypeError to be raised at runtime.

  Now, you aren't actually returning anything, but your type hinting is saying that you are. If you're going to use type hinting, the hints should make it clearer what types are involved, not make false claims.

• __iter__ should return an iterator:

  This method should return a new iterator object that can iterate over all the objects in the container

  The problem is, you're returning a list, and a list isn't an iterator, it's an iterable (it has an iterator). This isn't just a theoretical problem. Note how this can bite you:

  class T: def __iter__(self): return [1, 2, 3] for n in T(): print(n) # TypeError: iter() returned non-iterator of type 'list' 

Use of "dunder" methods can be helpful for writing clean code, but only if you aren't abusing them. Make sure to read the documentation and understand the purpose and contracts of methods before attempting to use them.

---

And on the subject of type hints, you could make use of a TypeVar to allow the type checker to see the consistency between the element types going in and out of your sorting function. After making your class into a standalone function, you basically have:

def selection_sort(input_list: list) -> list: 

The problem with this is, it doesn't tell the checker what the relationship is between the types of elements in input_list and that of the list that selection_sort returns. This can lead to subtle issues where it won't be able to help you with types:

lst: List[int] = [1, 2, 3] sorted_list = selection_sort(input_list) x = sorted_list[0] # It has no idea what type x is 

You can fix this by introducing a TypeVar that tells it that the element type remains consistent. I'm also changing from using list to List since list doesn't seem to support generics yet:

from typing import List, TypeVar T = TypeVar("T") # The sort returns the same element type T that it received def selection_sort(input_list: List[T]) -> List[T]: . . . 

Now, it is able to infer the type of x, and can give you better completions and type warnings.

Answer 2

This is mostly pretty good. Only a couple of things:

Delete this -

 print(self.input_list) 

You should leave printing to the caller.

Also - why the class at all? This really boils down to a single function. You only have one member variable, and only one method.

There's another issue - this class results in "surprising mutation". Iterating over it modifies one of its members. This is another argument for a simple function. If you keep the class, you could possibly

• Cache the sorted output, as a separate list from the input list, and/or
• store a copy of the input list instead of the input list itself.

That last point speaks to another issue - you assume that you're being passed a list, which isn't strictly necessary; all you need is an iterable. If you create a list from the input, you place fewer demands on your caller.