[Algorithm] 정렬 - 삽입 정렬(Insertion Sort)

#요약

• Target과 그 이전 데이터들과 비교하며 정렬한다.
• 소규모 데이터에 효율적이다.

#구체적 설명

1. 두번째 요소부터 시작하여 배열을 순회
2. 현재 요소를 Target이라고 하고, Target 이전의 요소들과 비교
3. Target이 이전 요소보다 작으면, 이전 요소를 한 칸 뒤로 이동
4. 이를 Target이 이전 요소들보다 크거나 같을 때까지 반복하고, Target을 적절한 위치에 삽입
5. 모든 요소에 대해 위 과정을 반복

#알고리즘

https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-6.php

#코드 작성

import java.util.Arrays;

public class SortAlgorithm {
    static int[] arr = new int[]{7, 1, 3, 2, 4, 5, 6};
    static int cnt = 0;

    public static void main(String[] args) {
        interSectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void interSectionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {

            int target = arr[i];
            int j = i - 1;

            while (j >= 0 && target < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = target;
        }
    }
}

#결과

[1, 2, 3, 4, 5, 6, 7]

#시간복잡도

최선	O(n)
평균	O(n2)
최악	O(n2)

#장단점

장점	단점
- 제자리 정렬	- 비효율적