삽입 정렬

특징

• 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식
• 알고리즘 복잡도: O(n^2)

정렬 과정

소스코드

    // 삽입 정렬(오름차순)
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {  //i는 1부터 끝까지
            for (int j = i; j > 0; j--) {   //j는 i부터 맨 앞까지
                if (arr[j] < arr[j - 1]) {  //arr[j]가 arr[j-1]보다 작으면 교체
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                } else {    //아니면 반복문 탈출. 앞에 수들은 이미 정렬되어있기 때문
                    break;
                }

            }
        }
    }