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!

--

--

--

Software Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Announcement about the temporary suspension of Zenlink SlotVault launch

Laybuy against Prestashop

7 Common Types Of Software Testing

The 12 Rules of Agile

3 key patterns of software resilience

What is Infrastructure as Code? Best Practises | Benefits | Adoption

Needleman-Wunsch Algorithm

Hack: How to Use SecureRandom with Kubernetes and Docker

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Thomas Muscarello

Thomas Muscarello

Software Engineer

More from Medium

Union Find / Algorithm

Programming Problems #3 : Muddy City Problem

Add Two Linked List Numbers

From arrays to hash-tables: part 1