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.
""" 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])