[알고리즘] 삽입 정렬(insertion sort)

yujamint·2022년 7월 19일

Java ps 알고리즘

PS

목록 보기

5/9

삽입 정렬 (Insertion Sort)

삽입 정렬은 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬이다.

손 안의 카드를 정렬하는 방법과 유사하며, 무조건 위치를 교환하는 선택 정렬과 버블 정렬에 비해 다소 효율적이라고 볼 수 있다.

정렬 과정

오름차순을 기준으로 정렬한다
원소가 n개 있다고 가정

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
두 번째 자료는 첫 번째 자료와, 세 번째 자료는 첫 번째부터 두 번째 자료, 네 번째 자료는 첫 번째부터 세 번째 자료, i번째 자료는 첫 번째부터 (i-1)번째 자료까지 비교하며 삽입될 위치를 찾는다. 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

삽입 정렬 Java 코드

public void insertionSort() {
    int[] arr = new int[] {11, 7, 5, 6, 10, 9};
    //0번째 인덱스는 비교대상이 없으므로 1번쨰 인덱스부터 시작
    for (int i=1; i<arr.length; i++){
        int tmp = arr[i]; // 정렬방식에 따라 삽입될 숫자를 tmp 변수로 복사
        
        //0~i-1번 인덱스까지는 정렬된 상태이므로, i번 인덱스까지 포함돼서 0~i번 정렬되도록 j를 i-1부터 0까지로 설정
        int j;
        for(j=i-1; i>=0; i--){
            if(arr[j] > tmp) arr[j+1] = arr[j]; // tmp가 들어갈 위치를 찾기 위해 tmp보다 큰 수를 오른쪽으로 옮긴다.
            else break; // tmp보다 작은 수가 들어있는 인덱스를 만나면 정지
        }
        arr[j + 1] = tmp; // tmp보다 작은 수가 들어있는 인덱스의 바로 뒤에 tmp를 넣는다.
    }
}

i는 삽입하게 될 원소 인덱스이다. 삽입 정렬은 두 번째 인덱스부터 시작한다.
j는 i번째 인덱스의 원소를 삽입하기 위해 비교할 인덱스 번호이다. 0번 인덱스 ~ (i-1)번 인덱스까지는 정렬된 상태이다. 이 중에서 tmp보다 작은 원소를 만나게 되면 해당 원소 앞에 tmp가 삽입된다.

11 7 5 6 10 9
첫 번째 원소인 11은 비교대상이 없으므로 1번 인덱스 원소인 7부터 시작한다.

1회전 : 7을 11과 비교한다. 7이 더 작으므로 11을 오른쪽으로 한 칸 옮기고 7을 그 자리에 삽입한다.
결과 : 7 11 5 6 10 9
2회전 : 2번 인덱스 원소인 5를 0~1번 인덱스와 비교한다. 5는 11보다 작기 때문에 11을 오른쪽으로 한 칸 옮기고, 7보다도 작기 때문에 7도 오른쪽으로 한 칸 옮기고 7의 자리에 5를 삽입하다.
결과 : 5 7 11 6 10 9
3회전 : 3번 인덱스 원소인 6을 0~2번 인덱스와 비교한다. 6은 11과 7보다 작기 때문에 11과 7을 오른쪽으로 한 칸 옮기고, 6보다 작은 5를 만나면서 정렬이 종료되고 5의 오른쪽에 6을 삽입한다.(6보다 작은 5를 만나면서 자리가 정해진 것)
결과 : 5 6 7 11 10 9
4회전 : 4번 인덱스 원소인 10을 0~3번 인덱스와 비교한다. 10은 11보다 작기 때문에 11을 오른쪽으로 한 칸 옮기고 10보다 작은 7을 만나면서 정렬이 종료되고 7의 뒤에 10을 삽입한다.
결과 : 5 6 7 10 11 9
5회전 : 5번 인덱스 원소인 9를 0~4번 인덱스와 비교한다. 9보다 큰 원소인 10과 11을 오른쪽으로 옮기고 9보다 작은 7을 만나면서 정렬이 종료되고 7의 뒤에 9를 삽입한다.
결과 : 5 6 7 9 10 11