Insert the next element from the unsorted portion of the array into the correct position in the sorted portion of the array. # pseudocode More specifically, the procedure will be to compare the first element in the unsorted portion of the range with the last element in the sorted portion of the range, and swap if they are not sorted. Continue swapping, moving backwards through the array, until the element is in the correct order. Note that this approach, working backwards through the array, may not be obvious. You might instead imagine starting from the left since it is often easier to think in ascending order than descending order. Shifting from our usual mode of thinking to a machine's mode of thinking is part of the art of designing algorithms. Let's write the pseudocode for this procedure. ``` insert(A, j) for i = j - 1 down to 1: if A[i] > A[i + 1]: swap(A[i], A[i + 1]) else: break ``` Note that the primitive operation `swap()` has not been defined explicitly. When implementing this code, we'll need to find an efficient way of swapping elements in an array, which may be language dependent. In [[Python]] this could be as simple as `(lst[i], lst[j]) = (lst[j], lst[i])`. To check that our procedure will work, consider the array ```python [3, 9, 12, 32, 11, ...] ``` where the unsorted portion begins with the $5th$ element $11$. The algorithm will run through each $i$ from $j-1=4$ to $1$, returning the result shown in the table below until element $A[i] \ge A[i + 1]$, which indicates it is in the correct order. | $i$ | $A[i]$ | $A[i+1]$ | `return` | | :-: | :----: | :------: | ------------------------- | | 4 | 24 | 10 | `[3, 9, 12, 11, 32, ...]` | | 3 | 15 | 10 | `[3, 9, 11, 12, 32, ...]` | | 2 | 7 | 10 | `break` | | 1 | -- | -- | -- | We can see that yes, the algorithm halts when the element in the $jth$ position is in the correct order. The next step in our pseudocode will be to repeat the procedure for all elements of the array, simply ``` for j = 1 up to n: insert(A, j) ``` Finally, we'll need to consider how the algorithm will function for the first and last element of the array. # computational complexity Computational complexity includes both time complexity and space complexity. How long does the algorithm take to run and how much memory does it require? We can also consider the best case complexity and worst case complexity. Usually we are interested in worst case complexity. Best case complexity is often considered too self serving. Average case complexity may also be considered but it is often roughly as bad as the worst case. In the case of the procedure `insert(a, j)`, we have four operations: each iteration of the for loop, the comparison, the swap, and the break. We can assign a constant unit of time to each operation $c_1$, $c_2$, $c_3$, and $c_4$, respectively. In the best case, element $j$ is already sorted. The algorithm will break in the first iteration of the for loop. This will incur the cost of the for loop, comparison for the $jth$ element with the $ith$ element, and finally the break, which is $c_1 + c_2 + c_4$. In the worst case, the $jth$ element is the lowest element in the array. It will need to be swapped with every element. In this case, the cost includes running the for loop, the comparison, and the swap $j - 1$ times, which is $(j - 1)(c_1 + c_2 + c_3)$. In Big Theta notation, the best case is $\Theta(1)$ or constant time whereas the worst case is $\Theta(j)$. Now let's consider the entire array. In the best case, the entire array is already in order and so we simply repeat the cost of the `insert(A, j)` for the best case $n$ times, or $n(c_1 + c_2 + c_3)$, or $\Theta(n)$ which is linear time. In the worst case, the array is in exactly the reverse order. We repeat the cost of the `insert(A, j)` for the worst case $n$ times. This will be $\sum_{j=1}^n (j-1)(c_1 + c_2 + c_3) = \frac{n(n-1)}{2}(c_1 + c_2 + c_3)$ which is asymptotically $\Theta(n^2)$ or quadratic time. Intuitively, you might guess that anytime an algorithm must do elementwise comparison for every element in an array, the time complexity will be $\Theta(n^2)$. > [!NOTE] > In [[Python]], there are two differences from the pseudocode, namely that in Python, the right endpoint is exclusive and array indices start from 0.