Insertion and Selection

Oh, did you think I was done with sorting? This blog is going to cover two more sorting styles: Insertion and Selection as well as compare all 3 in terms of Big O. To begin, let’s discuss Selection Sort.

Selection Sort is similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position. It still moves from the beginning to end of an array. However, as it compares the first element in an array to the other elements in an array, it only swaps positions when it finds the minimum per iteration.

For example is you wanted to sort the following array [5,3,4,1,2] while using selection sort, after the first pass, the array will look like: [1,3,4,5,2]. Then the following until it is done:[1,2,4,5,3] to [1,2,3,5,4] to [1,2,3,4,5].Once there are no more swaps needed, the array is fully sorted.

Our next sorting is Insertion Sort. With Insertion Sort, the array is sorted gradually by creating a larger half which is always sorted. It begins by comparing the first two elements and puts them in order. Then, with the first two elements sorted, it moves to the third element and sorts it to fit within the first two… and so on. For example, if we wanted to sort the following array with insertion: [5,3,4,1,2]. The arrays will look as followed:

[3,5,4,1,2] to [3,4,5,1,2] to [1,3,4,5,2] to [1,2,3,4,5].

The Big O complexity with each are slightly different. Below you will find the grid.

I still have a few more sorting techniques to go over so stay tuned!