LEARNING JOURNAL

One interesting thing about selection sort and insertion sort is that the first one costs N^2/2 whereas the second one costs N^2/4.

In selection sort, we need to compare the current element with all of the elements after it. The reason we need to compare all the elements is that the right portion of the array is not sorted, thus, we don't know when to stop, because if we stop before we reach the last element, the last element might be the one that we are looking for.

In insertion sort, we only need to compare the current element to the elements before we reaches its correct place in the array. We don't need to compare all because the left portion of the array is already sorted. We know when to stop.

To look at it in another way, in selection sort, we have the place (where the pointer is pointing), and we look for the element that should be in that place. Because the portion we are looking at is not sorted, we need to look at all the elements. In insertion sort, we have the element (which is pointed at by the pointer), we need to look for its place. Because the portion that we are looking at is sorted, we know exactly where its place is when we encounter it.