[알고리즘] 삽입정렬(Insertion Sort)

저번시간의 선택정렬에 이어서 이번시간에는 삽입정렬에 대해서 알아 보겠습니다. 사실 이름만 보아도 대충 어떤식으로 돌아가는지 알 수 있습니다. 

 

삽입정렬은 원소를 정렬되어 있는 구역의 알맞은 위치에 삽입하는 정렬방식입니다. 1 3 5 7 11 라는 정렬되어 있는 구역이 있고 그 다음 숫자가 2일 때 2의 들어갈 위치, 1과 3사이에 삽입해주면 됩니다.

 

이번 시간에도 마찬가지로 운동장에서 선생님이 학생들을 키 순으로 줄을 세울건데, 삽입정렬 방식으로 영호(175),호진(178),태경(180),웅광(167),동욱(173) 5명의 학생들을 키 순서대로 줄을 세울 생각입니다.

 

여기서 화살표는 현재 기준학생, "[]"표시는 이미 정렬되어 있는 학생들 구역이라고 생각하시면 됩니다. 기준 학생을 정렬되어 있는 구역의 적절한 위치에 삽입시키는 것이 삽입정렬의 방식입니다.

 

처음에는 정렬되어 있는 구역이 없네요. 영호를 넣고 넘어갑니다.

 

다음으로 호진이를 정렬되어 있는 구역에 넣어봅시다. 영호 오른쪽에 들어가니깐 구역이 정렬되었네요.

 

다음으로 태경이를 정렬되어 있는 구역에 넣어봅시다. 호진이 오른쪽에 들어가니깐 구역이 정렬되었네요.

 

다음으로 웅광이는 정렬되어 있는 구역에 넣어봅시다. 웅광이는 태경이보다 작은데 오른쪽에 있네요. 정렬 조건이 만족하지 않습니다. 이 둘 자리를 바꿉니다. 그런데 웅광이는 호진이보다 키가 작은데 오른쪽에 있네요. 또 자리를 바꿉니다. 마찬가지로 웅광이는 영호보다 키가 작은데 오른쪽에 있네요. 자리를 바꿉니다. 그러면 이제 정렬이 되었죠 ?

 

다음으로 동욱이를 정렬되어 있는 구역에 넣어봅시다. 구역에 정렬되지 않았네요. 다시 자리를 바꿉니다. 동욱이는 자기한테 맞는 자리를 찾아갈떄까지 자리를 계속 바꿀 것입니다. 

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       int[] ary = {1,5,6,2,7,8,10,21};

       
       for(int a=0;a<ary.length;a++){
         for(int b=a;b>=1;b--){
           if(ary[b-1]>ary[b]){
             int temp;
             temp=ary[b-1];
             ary[b-1]=ary[b];
             ary[b]=temp;
           }else{
             break;
           }
         }
       }
          for(int r:ary){
            System.out.println(r);
          }
    }
}

먼저 바깥for문은 기준값을 선택합니다. 안쪽 for문은 기준값을 기준으로 왼쪽편(정렬되어 있는 구역)의 값들을 하나씩 보면서 자신보다 큰 값이 있으면 바꿉니다(동욱이가 태경이, 호진이, 영호와 자리를 바꾸는 것처럼 말이죠). 그러다 자신보다 작은 값이 만나면 안쪽 for문을 빠져 나옵니다.

 

if(ary[b-1] > ary[b])은 기준값보다 정렬되어 있는 구역의 마지막 값(기준값의 바로 왼쪽)이 더 크면 값을 바로 바꿉니다. 만약 그렇지 않고 기준값이 기준값의 바로 왼쪽값보다 크면 넣을 필요가 없겠죠.

 

시간 복잡도는 선택정렬과 마찬가지로 기준값을 찾는데 O(n)번이 걸리고 그 기준값에서 정렬되어 있는 구역에 삽입할 위치를 찾는데 n번 반복해야 하기 때문에 O(n^2)가 나오게 됩니다.