삽입 정렬 (Insertion Sort)

삽입 정렬

- 손 안의 카드를 정리하는 방법과 유사한 정렬 방법

- 새로운 카드를 발견하면 그간 눈에 본 앞의 카드들을 보고 맞는 자리에 넣어 준다.

- 두번째 자리부터 시작해서 앞쪽의 원소와 비교하여 올바른 자리에 넣는 알고리즘

- 최선의 경우가 O(N)이라는 좋은 효율을 가지고 있기 때문에 다른 정렬 알고리즘에 사용되기도 한다.

 

정렬 알고리즘 (오름차순)

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

1. 두 번째 자리에 있는 원소를 key 원소로 선택한다.

2. key 원소 앞에 있는 원소와 하나씩 비교하면서 key 값 보다 큰 원소들은 하나씩 뒤로 밀어준다.

3. key 보다 작은 원소를 발견하면 그 바로 뒤 자리에 key 원소를 넣어준다.

4. 앞의 배열들은 오름차순으로 배열되있다는 것이 확정적이기 때문에 위와 같은 방법을 쓸 수 있다.

5. 반복

 

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class InsertionSort {
    public static void insertionSort(int arr[]) {
        int idx,tmp;
        for (int i = 1; i < arr.length; i++) {
            tmp = arr[i];
            idx = i-1;
            while (idx >= 0 && arr[idx] > tmp) {
                arr[idx+1] = arr[idx];
                idx--;
            }
            arr[idx+1] = tmp;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int _loop = Integer.parseInt(br.readLine());

        int arr[] = new int[_loop];
        for (int i = 0; i < _loop; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();

        insertionSort(arr);

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();
    }
}