Sorting Algorithms (Python)

Question

Selection Sort

The selection sort algorithm sorts a list (array) 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.

• The already sorted sub-list

• The remaining unsorted sub-list

Bubble Sort

The Bubble Sort algorithm functions by repeatedly swapping the adjacent elements, if they aren't in order.

Optimized Bubble Sort

An optimized version of Bubble Sort algorithm is to break the loop, when there is no further swapping to be made, in one entire pass.

Insertion Sort

Insertion sort algorithm builds the final sorted array in a one item at a time manner. It is less efficient on large lists than more advanced algorithms, such as Quick Sort, Heap Sort or Merge Sort, yet it provides some advantages, such as implementation simplicity, efficiency for small datasets and sorting stability.

---

I've been trying to implement the above algorithms in Python, practicing some object-oriented programming also, and I'd appreciate it if you'd review it for changes/improvements.

Code

from typing import List, TypeVar
T = TypeVar('T')
class InPlaceSortingAlgorithm(object):
 def __init__(self) -> None:
 pass
 def selection_sort(self, input_list: List[T]) -> List[T]:
 """
 This method 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 duplicate elements is not preserved)
 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.
 length = len(input_list)
 # Iterates through the list to do the swapping. 
 for element_index in range(length - 1):
 min_index = element_index
 # Iterates through the list to find the min index.
 for finder_index in range(element_index+1, length):
 if input_list[min_index] > input_list[finder_index]:
 min_index = finder_index
 # Swaps the min value with the pointer value.
 if element_index is not min_index:
 input_list[element_index], input_list[min_index] = input_list[min_index], input_list[element_index]
 return input_list 
 def length_of_array(self, input_list: List[T]) -> int:
 """
 Returns the length of the input array.
 """
 return len(input_list)
 def bubble_sort(self, input_list: List[T]) -> List[T]:
 """
 This method returns an ascending sorted integer list
 for an input integer list using regular Bubble Sort algorithm.
 Sorting: 
 - In-Place (Space Complexity => O(1))
 - Efficiency (Time Complexity => O(N^2))
 - Stable Sort (Order of equal elements does not change)
 """
 length = self.length_of_array(input_list)
 for i in range(length -1 ):
 for j in range(length - i - 1):
 if input_list[j] > input_list[j+1]:
 self.__swap_elements(j, j+1)
 return input_list
 def optimized_bubble_sort(self, input_list: List[T]) -> List[T]:
 """
 This method returns an ascending sorted integer list
 for an input integer list using an Optimized Bubble Sort algorithm.
 For optimization, the Bubble Sort algorithm stops if in a pass there would be no further swaps
 between an element of the array and the next element.
 Sorting: 
 - In-Place (Space Complexity => O(1))
 - Efficiency (Time Complexity => O(N^2))
 - Stable Sort (Order of equal elements does not change)
 """
 # Assigns the length of to be sorted array
 length = self.length_of_array(input_list)
 for i in range(length -1 ):
 number_of_swaps = 0
 for j in range(length - i - 1):
 if input_list[j] > input_list[j+1]:
 self.__swap_elements(j, j+1)
 number_of_swaps += 1
 # If there is no further swap in iteration i, the array is already sorted.
 if number_of_swaps == 0:
 break
 return input_list
 def __swap_elements(self, current_index: int, next_index: int) -> None:
 """
 Swaps the adjacent elements.
 """
 input_list[current_index], input_list[next_index] = input_list[next_index], input_list[current_index]
 def insertion_sort(self, input_list: List[T]) -> List[T]:
 """
 Iterates through the input array and sorts the array.
 """
 # Assigns the length of to be sorted array
 length = self.length_of_array(input_list)
 # Picks the to-be-inserted element from the right side of the array, starting with index 1.
 for i in range(1, length):
 element_for_insertion = input_list[i]
 # Iterates through the left sorted-side of the array to find the correct position for the element to be inserted.
 j = i - 1
 while j >= 0 and input_list[j] > element_for_insertion: 
 input_list[j+1] = input_list[j]
 j -= 1
 # Inserts the element.
 input_list[j+1] = element_for_insertion
 return input_list
if __name__ == "__main__":
 OBJECT = InPlaceSortingAlgorithm()
 TEST_LIST_1 = [10, 4, 82, 9, 23, -30, -45, -93, 23, 23, 23, 0, -1]
 # Tests the Selection Sort method
 print(OBJECT.selection_sort(TEST_LIST_1))
 # Tests the Optimized Bubble Sort method
 print(OBJECT.optimized_bubble_sort(TEST_LIST_1))
 # Tests the Bubble Sort method
 print(OBJECT.bubble_sort(TEST_LIST_1))
 # Tests the Insertion Sort method
 print(OBJECT.insertion_sort(TEST_LIST_1))

Input for Testing

[10, 4, 82, 9, 23, -30, -45, -93, 23, 23, 23, 0, -1]

Output

[-93, -45, -30, -1, 0, 4, 9, 10, 23, 23, 23, 23, 82]

References

• Selection Sort Algorithm (Python) - Code Review
• Bubble Sort (Geeks for Geeks)
• Bubble Sort (Wiki)
• Selection Sort (Geeks for Geeks)
• Selection Sort (Wiki)
• Insertion Sort (Wiki)

Answer 1

Use of classes / methods

• The InPlaceSortingAlgorithm class does not have any data / attributes associated to specific objects. Unlike some OO languages like Java, Python supports top-level function definitions. Therefore there is no real need for a class. If the intention is to group a bunch of reusable methods having similar functionality, create a module and import it from other files.

• I do not see a need for the wrapper method length_of_array. If you do not intend to modify the behaviour of the built-in len function, just use len. Also, the selection_sort method directly calls len, which is inconsistent with other methods, which call length_of_array instead.

• The input_list variable is not defined in the __swap_elements method. The method is not functional.

Issues of testing code

• In the test code, TEST_LIST_1 is sorted in-place by OBJECT.selection_sort. Afterwards, all the remaining methods receive inputs that are already sorted. That is why __swap_elements is never called and the program still runs. To fix this, a copy should be created for each function call using either TEST_LIST_1.copy() or TEST_LIST_1[:].

• For more extensive testing, input lists can be randomly generated and the results can be compared with the outcomes of the built-in sorted function.

Coding Style

• The style of using whitespaces in expressions are not consistent. Some expressions have whitespaces besides operators (e.g., range(length - 1)) while others do not (e.g., range(element_index+1, length)). The style should be consistent throughout the program.

• See PEP-8 for more Python style convensions. You can also choose an IDE that has built-in PEP8 inspection or use this website to check the style violations yourself.