삽입정렬

삽입정렬

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다. 

 

 

구현 예시

0) 0번째 인덱스가 아닌 1번째 인덱스부터 시작한다. 원소 5를 기준으로 자신의 위치 앞의 '7' 원소의 왼쪽/오른쪽 둘 중 선택하여 삽입된다.

- 원소 '5'는 원소 '7'보다 작으므로 '7'의 왼쪽에 삽입된다.

https://freedeveloper.tistory.com/274?category=888096

 

1) 2번째 원소인 '9'가 앞의 원소인 '7', '5'의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다.

https://freedeveloper.tistory.com/274?category=888096

 

2) 3번째 원소인 '0'이 앞의 원소 '9', '7', '5' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다.

https://freedeveloper.tistory.com/274?category=888096

 

3) 4번째 원소인 '3'이 앞의 원소 '9', '7', '5', '0' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다.

https://freedeveloper.tistory.com/274?category=888096

 

4) 이러한 과정이 반복된다.

https://freedeveloper.tistory.com/274?category=888096

 

 

예제코드

import java.util.stream.IntStream;

public class M10_삽입정렬 {
    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 0; i < n; i++) {
            // 인덱스 i 부터 1까지 감소하며 반복하는 문법
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    // swap
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                    break;
                }
            }
        }

        IntStream.range(0, n).mapToObj(i -> arr[i] + " ").forEach(System.out::println);
    }
}