>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] >>> insertion_sort(array, 0, len(array)) [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] >>> array = [21, 15, 11, 45, -2, -11, 46] >>> insertion_sort(array, 0, len(array)) [-11, -2, 11, 15, 21, 4
(array: list, start: int = 0, end: int = 0)
| 8 | |
| 9 | |
| 10 | def insertion_sort(array: list, start: int = 0, end: int = 0) -> list: |
| 11 | """ |
| 12 | >>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] |
| 13 | >>> insertion_sort(array, 0, len(array)) |
| 14 | [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] |
| 15 | >>> array = [21, 15, 11, 45, -2, -11, 46] |
| 16 | >>> insertion_sort(array, 0, len(array)) |
| 17 | [-11, -2, 11, 15, 21, 45, 46] |
| 18 | >>> array = [-2, 0, 89, 11, 48, 79, 12] |
| 19 | >>> insertion_sort(array, 0, len(array)) |
| 20 | [-2, 0, 11, 12, 48, 79, 89] |
| 21 | >>> array = ['a', 'z', 'd', 'p', 'v', 'l', 'o', 'o'] |
| 22 | >>> insertion_sort(array, 0, len(array)) |
| 23 | ['a', 'd', 'l', 'o', 'o', 'p', 'v', 'z'] |
| 24 | >>> array = [73.568, 73.56, -45.03, 1.7, 0, 89.45] |
| 25 | >>> insertion_sort(array, 0, len(array)) |
| 26 | [-45.03, 0, 1.7, 73.56, 73.568, 89.45] |
| 27 | """ |
| 28 | end = end or len(array) |
| 29 | for i in range(start, end): |
| 30 | temp_index = i |
| 31 | temp_index_value = array[i] |
| 32 | while temp_index != start and temp_index_value < array[temp_index - 1]: |
| 33 | array[temp_index] = array[temp_index - 1] |
| 34 | temp_index -= 1 |
| 35 | array[temp_index] = temp_index_value |
| 36 | return array |
| 37 | |
| 38 | |
| 39 | def heapify(array: list, index: int, heap_size: int) -> None: # Max Heap |