The Insertion sort is another simple sorting algorithm, which can be used to sort any linear data structure like an array or linked list. On simplicity, this is next to bubble sort, and it’s also pretty close to how humans manually sort something (for example, a hand of playing cards). As the name suggest, Insertion sort is based upon insertion of an element in a sorted list. To start, we assume that first element is already sorted. Then we pick the next element and put it in second place, we compare this number with the first element and if they are not in sorted order, we swap them. This gives a new sorted list of 2 elements. Now we pick the third element and put it in the 3rd place and compare it with the 2nd placed number, if they are not in sorted order, we swap them again, if all three elements are still not in sorted order then we again swap the 1st and 2nd element, now we have a sorted list of three numbers.
Difference between Comparison (QuickSort) and Non-Comparison (Counting Sort) based Sorting Algorithms?
For many of you, this might be a surprise that how you can sort or arrange items without comparing with each other, but it's possible. There are some sorting algorithms that perform sorting without comparing the elements rather by making certain assumption about the data they are going to sort. The process is known as non-comparison sorting and algorithms are known as the non-comparison based sorting algorithms. No comparison sorting includes Counting sort which sorts using key value, Radix sort, which examines individual bits of keys, and Bucket Sort which examines bits of keys. These are also known as Liner sorting algorithms because they sort in O(n) time. They make certain assumption about data hence they don't need to go through comparison decision tree.
I have shared a lot of books related to Java and related technologies in the past e.g. Spring, Hibernate, JVM internals and performance tuning, multi-threading and concurrency, design patterns, data structure and algorithms etc, but I haven't shared core Java books for beginners yet. Even though I have mentioned a couple of popular titles every now and then, I really didn't have a good compilation of essential core Java books for beginners. Since Java is one of the most popular programming languages and has very good job prospect it has became a choice of programming language to start learning coding and application development, it makes sense to start well with core Java. This article contains books which will teach you how to code using Java programming language.