what is Insertion Sort algorithm

what is Insertion Sort algorithm

  3월 01, 2022    Eunhan's library

---

Insertion Sort

Definition

one way of sorting algorithms by using brute force.
check every possible ways to sort the list.

Algorithm steps

1. There are two position. one is for moving the other one is for checking
2. When you check two values, smaller go to left side
3. These two positions checking started from original position.
4. set moving position is original position and checking position is original position-1
5. These two positions checking getting smaller untill the checking position reached to 0
6. Repeat 1~6 until all of them sorted.

Java code

    private static int[] insertSort(int[] input) {
        if (input.length < 2) {
            return input;
        }

        for (int originalPosition = 1; originalPosition < input.length; ++originalPosition) {
            int movingPostion = originalPosition;
            int checkingPostion = originalPosition - 1;

            while (checkingPostion > 0) {
                if (input[checkingPostion] > input[movingPostion]) {
                    swap(input, checkingPostion, movingPostion);
                } else {
                    break;
                }
                --checkingPostion;
                --movingPostion;
            }
        }
        return input;
    }

    private static void swap(int[] input, int pos1, int pos2) {
        int temp = input[pos2];
        input[pos2] = input[pos1];
        input[pos1] = temp;
    }

Avg. time complexity

$O(n^2)$

Worst time complexity

$O(n^2)$

space complexity

$O(1)$

stability

no