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

1. 정의

삽입 정렬(Insertion Sort)는 비교적 간단한 정렬 방법 중 하나이다. 삽입 정렬에서의 가장 중요한 규칙은 다음과 같다.

- 현재 선택된 데이터 이전의 데이터들은 항상 정렬된 상태이다.

좀 더 알기 쉽게 그림으로 표현하자면, 다음과 같을 것이다.

이를 만족하는 상태로 데이터를 재정렬하는 과정을 삽입 정렬(Insertion Sort)라고 한다.

2. 설명

PASS 1

삽입정렬은 두번째 Index부터 시작된다. 제일 앞의 원소는 원소가 하나이기 때문에, 그 자체로 정렬된 상태이기 때문이다.

우선, 4 와 2 의 크기를 비교해, 4 > 2 이므로, 2의 위치를 찾아 삽입해준다.

PASS 2

두번째로 5 가 선택된다. 5 앞의 정렬된 데이터의 최대값 4 보다 5 가 크므로, 현위치에 둔다.

PASS 3

PASS 2와 같은 경우다. 선택된 데이터인 6 이 앞서 정렬된 데이터의 최대값 5 보다 크므로, 현위치에 둔다.

PASS 4

4번째로, 데이터 1 이 선택되었다.

1 의 위치를 찾는 방법은 우선 6 과 비교한다. 6 보다 1 이 작기 때문에 두 데이터의 위치를 바꾼다. 다음으로 1 과 5 를 비교한다. 마찬가지로, 5 보다 1 이 작기 때문에, 또 위치를 바꾼다.

    

위의 과정을 거쳐 최종적으로는 아래의 모습이 될 것이다.

PASS 5

마지막으로 데이터 3 이 선택되었다.

3 의 위치도 PASS 4의 방법과 동일하게 찾는다. 그런 과정을 거치면 아래와 같이 완벽하게 정렬된 데이터를 얻을 수 있다.

3. 코드

for(i=1;i<Len;i++){//Len은 정렬할 데이터 수    
    for(j=i;data[j]<data[j-1] && j>0;j--){
        int temp=data[j];
        data[j]=data[j-1];
        data[j-1]=temp;
    }
}

다른 정렬 알고리즘 보기