pysorting.insertionsort
This module implements the insertion sort algorithm in python. Insertion sort is a basic algorithm that sorts a list of data by taking each element one by one, comparing it to the element to its left, swapping the value if it is larger, until it finds a smaller element. then it increments and begins again for the next element. @author: Marek Boulerice
Functions
|
Sorts a list of numbers in ascending or descending order using the Insertion Sort algorithm. |
Module Contents
- pysorting.insertionsort.insertion_sort(arr, ascending=True)[source]
Sorts a list of numbers in ascending or descending order using the Insertion Sort algorithm.
This function takes a single list as a parameter and performs insertion sorting using the following algorithm. It begins with the second item in the list and compares its value to the item immediately to its left. If the value is smaller, it swaps the two items. If the value is larger than the item to its left, or if the item is in the first position, the function stops. Otherwise, it continues comparing and swapping as needed. The process is repeated for each subsequent item in the list until all items have been checked. After completing the sorting process, the function returns the newly sorted array.
Parameters:
- arrlist
The list of numeric values to be sorted.
- ascendingbool, optional
If True (default), sorts the list in ascending order. If False, sorts the list in descending order.
Returns:
- list
The sorted list in ascending order if ascending=True, or in descending order if ascending=False.
Raises:
- TypeError
If the input is not a list.
- InvalidElementTypeError
If the list contains non-numeric elementsor string values.
- NonUniformTypeError
If the list contains more than one form of data type
Notes:
Insertion Sort is a simple sorting algorithm with a time complexity of O(n^2) for average and worst cases.
This algorithm is inefficient for large datasets but can be used for educational purposes or small lists.
Sorting in descending order is achieved by reversing the comparison logic during the sorting process.
Examples:
Sorting in ascending order (default):
>>> insertion_sort([4, 2, 7, 1, 3]) [1, 2, 3, 4, 7]
Sorting in descending order:
>>> insertion_sort([4, 2, 7, 1, 3], ascending=False) [7, 4, 3, 2, 1]