{
"properties": {
"score": 0.5081191062927246,
"page_number": 4,
"page_numbers": [
4
]
},
"type": "Section",
"binary_representation": null,
"text_representation": "4 \n\nLecture 3: Sorting \n\nInsertion Sort \n\n\u2022 Recursively sort pre\ufb01x A[:i] \n\n\u2022 Sort pre\ufb01x A[:i + 1] assuming that pre\ufb01x A[:i] is sorted by repeated swaps \n\n\u2022 Example: [8, 2, 4, 9, 3], [2, 8, 4, 9, 3], [2, 4, 8, 9, 3], [2, 4, 8, 9, 3], [2, 3, 4, 8, 9] \n\n1 def insertion_sort(A, i = None): \n\u2019\u2019\u2019Sort A[:i + 1]\u2019\u2019\u2019 \n2 \nif i is None: i = len(A) - 1 \nif i > 0: \n 3 \n 4 \n 5 \n 6 \n insertion_sort(A, i - 1) \ninsert_last(A, i) \n 7 \n8 def insert_last(A, i): \n9 \n \u2019\u2019\u2019Sort A[:i + 1] assuming sorted A[:i]\u2019\u2019\u2019 \nif i > 0 and A[i] < A[i - 1]: \n A[i], A[i - 1] = A[i - 1], A[i] \ninsert_last(A, i - 1) \n 10 \n 11 \n 12 \n # T(i) \n # O(1) \n# O(1) \n# T(i - 1) \n# S(i) \n # S(i) \n # O(1) \n# O(1) \n# S(i - 1) \n\n\u2022 insert last analysis: \n\n\u2013 Base case: for i = 0, array has one element so is sorted \n\n\u2013 Induction: assume correct for i, if A[i] >= A[i - 1], array is sorted; otherwise, \n swapping last two elements allows us to sort A[:i] by induction \n\n\u2013 S(1) = \u0398(1), S(n) = S(n \u2212 1) + \u0398(1) =\u21d2 S(n) = \u0398(n) \n\n\u2022 insertion sort analysis: \n\n\u2013 Base case: for i = 0, array has one element so is sorted \n\n\u2013 Induction: assume correct for i, algorithm sorts A[:i] by induction, and then \n insert last correctly sorts the rest as proved above \n\n\u2013 T (1) = \u0398(1), T (n) = T (n \u2212 1) + \u0398(n) =\u21d2 T (n) = \u0398(n2) \n",
"bbox": [
0.11637571447035845,
0.09453096563165839,
0.8855567842371324,
0.7101616876775568
]
}