Please enable JavaScript.

Coggle requires JavaScript to display documents.

sorting algorithms (Insertion sort - efficient for small numbers of…

- - - - Maintenance - Each iteration of the loop expands the subarray, but keeps the sorted property. An element gets inserted into the array only when it is greater than the element to its left. Since the elements to its left have already been sorted, it means is greater than all the elements to its left, so the array remains sorted.
      - Termination - The code will terminate after has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. The array is now fully sorted.
      - Initialization - The subarray starts with the first element of the
        array, and it is (obviously) sorted to begin with.
      - state the following loop invariant: At the start of every iteration of the outer loop (indexed with i), the subarray until ar[i] consists of the original elements that were there, but in sorted order.
- - - - there are such types of Algorithmic paradigm: greedy algoritms, while solving optimization problems