삽입 정렬 (Insert Sort) - Java

삽입 정렬 메커니즘

1. 인덱스 1인  요소부터 정렬해야할 리스트를 순회한다. => 변수 i

 

2. 각 요소값인 arr[i] 에 대해 j 가 i-1 -> 0 까지 순회한다.

 

3. j 가 순회하면서 arr[i] 값과 비교

• arr[j] > arr[i]
  : j+1 위치의 값에 현재 j 위치의 값을 할당한다. 
  : 다시 말해, arr[j] 의 바로 오른쪽 값인 arr[j+1] 을 arr[j] 값으로 바꿔주는 것. 
  : i 위치의 왼쪽 요소들에 대해 순회하며 만약 해당 값이 arr[i] 보다 큰 값이라면 그 위치를 한 칸 오른쪽으로 미는 것과 같다. 

• arr[j] < arr[i]
  : 기준 값인 arr[i] 보다 작은 값이 발견되면 j 반복문을 종료한다 => break;

• j 에 대한 반복문이 종료된 후의 j 값
  1. -1  : arr[i] 왼쪽 요소들의 값이 모두 arr[i] 보다 큰 경우
  2. arr[i] 보다 작은 값을 갖고 있는 요소의 인덱스 값
  3. 그러므로 종료 후의 j 위치의 한 칸 오른쪽에 arr[i] 값을 할당해준다. 
  4. 그러면 작은 값이 등장한 위치의 바로 오른쪽에 arr[i] 값이 들어간 셈. 

 

4. i 가 마지막 요소까지 모두 순회하고 나면 모든 요소가 정렬된 상태가 된다. 

 

 

삽입 정렬 구현 코드

(i 와 j 가 헷갈려서 x, y 로 변경함)

public class Test {
    public static int[] solution(int[] arr) {
        for(int x = 1; x < arr.length; x++) {
            int tmp = arr[x];
            int y;
            for(y = x - 1; y >= 0; y--) {
                if(arr[y] > tmp) arr[y + 1] = arr[y];
                else break;
            }
            arr[y + 1] = tmp;
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] output = solution(new int[]{3, 1, 21});
        System.out.println(Arrays.toString(output));
    }
}

// 출력 결과
[1, 3, 21]