Insertion Sort – Java Implementation

What is Insertion Sort??

  1. Insertion sort is a simple sorting algorithm that builds the sorted array one item at a time.
  2. Efficient for small data sets, not efficient for large data sets.
  3. Most of the time we sort the playing cards in our hand using insertion sort without knowing about it.
  4. At any given time, your array will be partially sorted and partially unsorted. At the end, you will have fully sorted array.
  5. In every iteration, one element will be taken from unsorted array and placed at its right position in the sorted array. Iteration ends when there are no elements left in the unsorted array.

Pseudo Code:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

See the video below for more understanding.

Time Complexity: O(N2)

Java Code for Insertion Sort:

Output:

Original Array: [5, 1, 9, 3, 2, 10]
(Insertion Sort)- Sorted Array: [1, 2, 3, 5, 9, 10]

Reference: Wiki

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: