데일리썽

1. 삽입 정렬 (insertion sort)

삽입 정렬은 두 번쨰 인덱스부터 시작

해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서 key 값이 더 작으면 데이터 값을 뒤 인덱스로 복사

이용 Key 값이 더 큰 데이터를 만날떄까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

• [5, 3]
  -> [3, 5]
• [5, 3, 2]
  -> [3, 5, 2]
  -> [3, 2, 5] -> [2, 3, 5]
• [5, 3, 2, 4]
  -> [3, 5, 2, 4]
  -> [3, 2, 5, 4] -> [2, 3, 5, 4]
  -> [2, 3, 4, 5] -> [2, 3, 4, 5]

import java.util.*;

public class InsertionSort {
    public static void insertionSort() {
    	int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }

        System.out.println("정렬 후 : " + arr);
	}
}

2. 알고리즘 분석

반복문이 두개 : O(n^2)

완전 정렬이 되어 있는 경우 : O(n)