pytudes._2021.miscellany.insertion_sort

NOTE: - Contiguous slice update is O(k) where k = size of the slice

=> same big O as single-item swaps.

• Trivial overhead but improved readability for

  reversed(range)) vs. range(end, start-1, -1)

Module Contents

Functions

binary_insertion_sort(items)	Complexity:
insertion_sort(items)	Examples:
insertion_sort_loops_combined(items)	Args:

pytudes._2021.miscellany.insertion_sort.binary_insertion_sort(items)

Complexity:

Time: O(n^2) Space: O(1)

NOTE: since shifting dominates the runtime, allowing binary search subroutine to be Θ(logn) by not breaking early if items[mid_idx] == insertion_val.

This minimizes shift operations by ensuring items[mid_idx] is the smallest element strictly greater than insertion_val (i.e., the IMMEDIATE SUCCESSOR)

See Also:

• pytudes/_2021/educative/modified_binary_search/_3__next_letter__medium.py

Args:

items:

Returns: items sorted

Examples:

>>> binary_insertion_sort([5,4,3,2,1,0])
[0, 1, 2, 3, 4, 5]
>>> binary_insertion_sort([0,1,2,3,4,5])
[0, 1, 2, 3, 4, 5]
>>> binary_insertion_sort([5,4,3,2,1,0]*2)
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
>>> items = [random.randrange(0, 100) for _ in range(100)]
>>> assert(binary_insertion_sort(items.copy()) == sorted(items))

Parameters:

items (list) –

Return type:

list

pytudes._2021.miscellany.insertion_sort.insertion_sort(items)

Examples:

>>> items = [random.randrange(0, 100) for _ in range(100)]
>>> assert(insertion_sort(items.copy()) == sorted(items))

Parameters:

items (list) –

Return type:

list

pytudes._2021.miscellany.insertion_sort.insertion_sort_loops_combined(items)

Args:

items:

Returns:

Examples:

>>> items = [random.randrange(0, 100) for _ in range(100)]
>>> assert(insertion_sort_loops_combined(items.copy()) == sorted(items))

Parameters:

items (list) –

Return type:

list