{"id":19146,"date":"2020-12-01T04:12:21","date_gmt":"2020-12-01T12:12:21","guid":{"rendered":"https:\/\/careerkarma.com\/blog\/?p=19146"},"modified":"2023-12-01T04:05:07","modified_gmt":"2023-12-01T12:05:07","slug":"insertion-sort-java","status":"publish","type":"post","link":"https:\/\/careerkarma.com\/blog\/insertion-sort-java\/","title":{"rendered":"Insertion Sort in Java: A How-To Guide"},"content":{"rendered":"\n

A Java insertion sort evaluates each item in a list. If an item is less than the one before, the sort swaps the items. Otherwise, the items stay in the same place and the next two items are compared in the list.<\/p>\n\n\n\n

Computers are good at sorting lists of items. Using loops, you can search through all the items in a list and change their order until they appear a certain way.\n\n<\/p>\n\n\n\n

In programming, there are a few standard methods of sorting lists. We call these sort algorithms. Sort algorithms read through all the items in a list and sort them using a particular set of instructions. One of the most common sort algorithms you\u2019ll encounter is an insertion sort.\n\n<\/p>\n\n\n\n

In this guide, we\u2019re going to discuss how to implement a Java insertion sort algorithm. We\u2019ll walk through an example along the way so that you can learn how the logic behind this sort works.\n\n<\/p>\n\n\n\n

Let\u2019s get started!<\/p>\n\n\n\n

What is a Java Insertion Sort?<\/h2>\n\n\n\n

A Java insertion sort works similar to sorting cards in your hand in a card game. Insertion sorts check each item in a list and swaps them with an item to its left. Whether an item is swapped depends on if the item is greater than or less than previous items.\n\n<\/p>\n\n\n\n

Imagine, for a moment, that you are playing a card game \u2013 whist, rummy, whatever. When you\u2019re sorting your cards, what do you do?\n\n<\/p>\n\n\n\n

You will start at the left and check whether the second card is sorted. If that card is greater than the last, it should remain in the same position. Oherwise, it should move up a position in the list.\n\n<\/p>\n\n\n\n

You\u2019ll go through every card in your hand and perform this operation until every card appears in its right order.<\/p>\n\n\n\n

When Should You Use an Insertion Sort?<\/h2>\n\n\n\n

Insertion sorts are most used when there are only a few elements to the left that need to be sorted.<\/p>\n\n\n\n

There are more efficient algorithms that you can use to sort large lists of data, such as a merge sort. This is why you shouldn\u2019t always default to using an insertion sort. With that said, insertion sorts are more efficient than bubble sorts and selection sorts at sorting elements in a list.<\/p>\n\n\n\n

An insertion sort is a simple sorting algorithm which means it is good for beginners to learn.<\/p>\n\n\n\n

Insertion Sort Walkthrough<\/h2>\n\n\n\n

Visualizing a deck of cards isn\u2019t the most intuitive in the world. Let\u2019s walk through a programming example to get you started. Consider the following list:<\/p>\n\n\n\n
8<\/td>6<\/td>3<\/td>9<\/td><\/tr><\/tbody><\/table>\n\n\n\n

In this list, we assume the first element is sorted.\n\n<\/p>\n\n\n\n

Our next step is to compare the second item in our list with the first one. If the first item is greater than the second item, then that item is placed in front of the first item.\n\n<\/p>\n\n\n\n

In this case, 6 is greater than 8. This means that 6 will move back in our list by one position, and 8 will move forward by one position:\n<\/p>\n\n\n\n
6<\/td>8<\/td>3<\/td>9<\/td><\/tr><\/tbody><\/table>\n\n\n\n

Now we need to compare the third element with the elements to its left: Is 3 greater than 8? No, so 8 moves position to the right:<\/p>\n\n\n\n
6<\/td>3<\/td>8<\/td>9<\/td><\/tr><\/tbody><\/table>\n\n\n\n

Is 3 greater than 6? No, so we move the number 6:<\/p>\n\n\n\n
3<\/td>6<\/td>8<\/td>9<\/td><\/tr><\/tbody><\/table>\n\n\n\n

Now, we\u2019ve got to compare whether the fourth item in our list \u2013 the last item \u2013 is greater than every other item in our list. In this case, 9 is greater than all the items that come before it: 8, 6, and 3. \n\n<\/p>\n\n\n\n

Here\u2019s the algorithm that we have used to sort our list:\n\n<\/p>\n\n\n\n