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]
