[알고리즘] 정렬 알고리즘 - 1 (삽입 정렬)

[알고리즘] 정렬 알고리즘 - 1 (삽입 정렬)

 

이번 포스팅에서는 정렬 알고리즘에 대해 알아보도록 하겠습니다.

다음 교재를 참고하여 작성함을 미리 밝힙니다. 

쉽게 배우는 알고리즘 - 한빛아카데미

---

정렬이란 데이터를 특정한 조건(오름차순, 내림차순, 이름순, 시간순 등)에 따라 일정한 순서가 되도록 다시 배열하는 작업을 의미합니다. 정렬은 탐색의 기본이 되는 알고리즘입니다. 

이번 포스팅과 다음 포스팅에 이어서 정렬 기본 알고리즘인 삽입 정렬, 선택 정렬, 버블 정렬의 순서대로 알아보겠습니다.

 

• 삽입 정렬

삽입 정렬은 배열에서 정렬된 부분과 정렬 안 된 부분으로 나누어 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 "삽입"해 가면서 정렬을 진행합니다.

 

다음의 배열 [7, 1, 5, 3, 2]를 삽입 정렬로 정렬하는 과정을 나타내보겠습니다. 색이 칠해져 있는 부분이 정렬된 부분입니다.

초기 상태

7

1

5

3

2

 

step 1 (copy 1; shift 7; insert 1)

1

7

5

3

2

 

step 2 (copy 5; shift 7; insert 5)

1

5

7

3

2

 

step 3 (copy 3; shift 5,7; insert 3)

1

3

5

7

2

 

 

step 4 (copy 2; shift 3, 5, 7; insert 2)

1

2

3

5

7

         으로 칠해진 부분이 정렬된 부분입니다. 위와 같이 삽입정렬은 정렬된 부분과 정렬 안 된 부분으로 나눈 후 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복하며 정렬합니다.

 

 

삽입 정렬의 슈도코드를 살펴보겠습니다.

Insertion Sort

for $i \gets 2$ to $n$ 은 $i$를 $2$부터 $n$까지 늘리며 for문을 수행한다는 의미입니다.

 

다음의 삽입 정렬 코드로 살펴보겠습니다. C언어로 작성하였습니다.

 

 

#include <stdio.h>
void InserSort(int arr[], int n){
    int i, j;
    int insData;
    for(i = 1; i < n; i++){
        insData = arr[i]; //정렬 대상을 insData에 저장
        for(j = i - 1; j >= 0; j--){
            if(arr[j] > insData) //정렬 대상과 정렬된 배열의 원소 비교
                arr[j+1] = arr[j];
            else    //삽입 위치를 찾았을 때
                break; 
        }
        arr[j+1] = insData;
    }
}
int main(void) {
  int arr[5] = {7, 1, 5, 3, 2};
  int i;
  
  printf("Initial : ");
  for(i = 0; i < 5; i++){
      printf("%d", arr[i]);
  }
  InserSort(arr, sizeof(arr)/sizeof(int));
  
  printf("\n   Sort : ");
  for(i = 0; i < 5; i++)
    printf("%d", arr[i]);
  
  printf("\n");
  return 0;
}

출력 결과 >>