Member-only story
How to explain Insertion Sort in Java?
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. While the algorithm is not as fast or memory efficient compared to Quick Sort and Merge Sort when dealing with large size of data sets. However, insertion sort is a relatively efficient for a small data set and an import algorithm to known when you start to learn sorting algorithms.
What is Insertion Sort?
삽입 정렬을 한마디로 정의한다면 다음과 같습니다.
Divide into an organized and an unorganized list. Move the items/values from unorganized list into an organized list.
If we were to express this in a pseudocode, it will look like below.
for (each item x in unsorted list U) {
insert X into sorted list S in sorted order
}
Example:
Let’s say we have an unordered list like below:
U = [23, 42, 4, 16, 8, 15]
The size of list is 6, and the index goes from 0 to 5.
Let’s create an empty list S, which represents an organized list.
S = []
We will iterate to move each item from an unorganized list to an organized list. The result will look like below.
