정렬 - 삽입정렬

https://visualgo.net/en/sorting

1. 삽입 정렬

• 각 숫자를 적절한 위치에 삽입하는 방법
  → 무조건 위치를 바꾸는 선택정렬과 버블정렬과는 달리 필요할 때만 위치를 바꿈
  → 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교해서 자신의 위치를 찾아서 삽입
  → 5를 기준으로 봤을 때 들어갈 수 있는 곳은 → _ 1 _ 10 _ → 이렇게 3군데 중 가운데 삽입
  → 7의 경우 1 5 8 10 으로 앞부분이 정렬되어 있음 → 1 5 7 8 10 이렇게 삽입
  2번째 인덱스부터 시작하여 해당 인덱스(key) 값과 앞의 인덱스 값을 비교해서 key가 더 작으면 앞으로 이동
  → key값보다 더 큰 값을 만날때까지 반복 → 큰 데이터 값을 만난 위치 바로 뒤로 key값을 이동

2. 시간 복잡도 - O(n^2)

• 시간복잡도는 선택, 버블정렬과 같지만 속도는 삽입정렬이 가장 빠름
• 데이터가 거의 정렬이 되어 있는 상황에서는 퀵, 힙, 병합 정렬과 동일하거나 더 빠른 속도를 낼 수 있음

import java.util.ArrayList;

import static java.util.Collections.swap;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        int[] result = solution(arr);
        for (int x : result) {
            System.out.print(x + " ");
        }
        
        System.out.println();
        System.out.println("================================");
        
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(10);
        arrayList.add(5);
        arrayList.add(8);
        arrayList.add(7);
        arrayList.add(6);
        arrayList.add(4);
        arrayList.add(3);
        arrayList.add(2);
        arrayList.add(9);
        ArrayList<Integer> result2 = solution2(arrayList);
        for (Integer i : result2) {
            System.out.println(i);
        }
    }

    public static int[] solution(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int j = i;
            while (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                j--;
            }
        }

        return arr;
    }

    public static ArrayList<Integer> solution2(ArrayList<Integer> arrayList) {
        for (int i = 0; i < arrayList.size() - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arrayList.get(j) < arrayList.get(j - 1)) {
                    swap(arrayList, j, (j - 1));
                }else{
                    break;
                }
            }
        }
        return arrayList;
    }
}