There is a follow-up question available: shell-sort-insertion-sort-bubble-sort-selection-sort-algorithms-python.
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.
Bubble Sort
The Bubble Sort algorithm functions by repeatedly swapping the adjacent elements, if they aren't in correct 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.
Shell Sort (Optimized Insertion Sort)
Shell Sort is just a variation of Insertion Sort, in which the elements are moved only one position ahead. When an element has to be moved far ahead, too many movements are involved, which is a drawback. In Shell Sort, we'd make the array "h-sorted" for a large value of h. We then keep reducing the value of h (sublist_increment) until it'd become 1.
I've been trying to implement the above algorithms in Python and modified it based on prior reviews, I'd appreciate it if you'd review it for any other changes/improvements.
Code
import random
from typing import List, TypeVar
from scipy import stats
T = TypeVar('T')
def selection_sort(input_list: List[T]) -> List[T]:
"""
This method returns an ascending sorted integer list
for an input integer/float list using Selection Sort Algorithm.
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 bubble_sort(input_list: List[T]) -> List[T]:
"""
This method returns an ascending sorted integer list
for an input integer/float 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 = len(input_list)
for i in range(length - 1):
for j in range(length - i - 1):
if input_list[j] > input_list[j + 1]:
_swap_elements(input_list, j, j + 1)
return input_list
def optimized_bubble_sort(input_list: List[T]) -> List[T]:
"""
This method returns an ascending sorted integer list
for an input integer/float 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 = len(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]:
_swap_elements(input_list, 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(input_list: List[T], 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(input_list: List[T]) -> List[T]:
"""
This method returns an ascending sorted integer list
for an input integer/float list using a Insertion Sort algorithm.
Sorting:
- In-Place (space complexity O(1))
- Efficiency (time complexity O(N^2) - Good if N is small - It has too many movements)
- Stable Sort (Order of duplicate elements is preserved)
"""
# Assigns the length of to be sorted array.
length = len(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
def shell_sort(input_list: List[T], sublist_increment: int) -> List[T]:
if sublist_increment // 2 == 0:
print("Please select an odd number for sublist incrementation. ")
return
# Assigns the length of to be sorted array.
length = len(input_list)
while sublist_increment >= 1:
for i in range(sublist_increment, 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 - sublist_increment
while j >= 0 and input_list[j] > element_for_insertion:
input_list[j + sublist_increment] = input_list[j]
j -= sublist_increment
# Inserts the element.
input_list[j + sublist_increment] = element_for_insertion
# Narrows down the sublists by two increments.
sublist_increment -= 2
return input_list
if __name__ == "__main__":
# Generates a random integer list
TEST_LIST_INTEGER = random.sample(range(-1000, 1000), 15)
# Generates a random float list
TEST_LIST_FLOAT = stats.uniform(-10, 10).rvs(10)
print(f"The unsorted integer input list is:\n{TEST_LIST_INTEGER}\n-----------------------------------\n")
print(f"The unsorted float input list is:\n{TEST_LIST_FLOAT}\n-----------------------------------\n")
# Tests the Selection Sort Algorithm:
print("---------------------------------")
print(f"Selection Sort (Integer): {selection_sort(TEST_LIST_INTEGER.copy())}")
print(f"Selection Sort (Float): {selection_sort(TEST_LIST_FLOAT.copy())}")
# Tests the Optimized Bubble Sort Algorithm:
print("---------------------------------")
print(f"Optimized Bubble Sort (Integer): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
print(f"Optimized Bubble Sort (Float): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
# Tests the Bubble Sort Algorithm:
print("---------------------------------")
print(f"Bubble Sort (Integer): {bubble_sort(TEST_LIST_INTEGER.copy())}")
print(f"Bubble Sort (Float): {bubble_sort(TEST_LIST_INTEGER.copy())}")
# Tests the Insertion Sort Algorithm:
print("---------------------------------")
print(f"Insertion Sort (Integer): {insertion_sort(TEST_LIST_INTEGER.copy())}")
print(f"Insertion Sort (Float): {insertion_sort(TEST_LIST_INTEGER.copy())}")
# Tests the Shell Sort Algorithm:
print("---------------------------------")
print(f"Shell Sort (Integer): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")
print(f"Shell Sort (Float): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")
