[알고리즘] C언어 삽입정렬 구현(Insertion Sort) 소스코드

안녕하세요 오늘은 삽입정렬을 C언어로 구현해보겠습니다.

삽입정렬이란 기존의 배열의 모든 값을 앞부터 정렬된 배열과 비교하여 들어갈 위치를 찾고,

그 위치에 삽입하며 정렬해나가는 방법입니다.

바로 소스를 통해 알아보겠습니다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

#include <stdio.h>

int main(){

    int arr[5]={5, 16, 1, 4, 12};

    int temp;

    

    for(int i=0;i<4;i++){

        int j=i-1;

        while((arr[j] > arr[j+1])&&(j>=0)){

            temp=arr[j];

            arr[j]=arr[j+1];

            arr[j+1]=temp;

            j--;

        }

    }

    for(int i=0;i<5;i++){

        printf("%d\n",arr[i]);

    }

    

    return 0;

}

Colored by Color Scripter

cs

for문 안에 while문을 썼는데요, j번째 항과 j+1번째 항을 비교하여 

j번째 항(앞 항)이 j+1번째 항(뒷 항)보다 크게 되면 이 둘을 swap해줍니다. 

이 때, j는 i-1이므로 0보다 클때만 swap해 주어야겠죠?

이를 반복하게 되면 while문을 빠져나갈 때 해당되는 항이 앞의 정렬된 배열에서

자신이 들어갈 위치를 찾아 들어가게 됩니다.

순차적으로 확인해보면

최초 배열부터 for문을 한번씩 돌 때마다

5 16 1 4 12

5 16 1 4 12

1 5 16 4 12

1 4 5 16 12

1 4 5 12 16

위와같은 순서로 정렬이 됩니다.

실행결과를 확인해보겠습니다.

오름차순으로 정렬이 매우 잘 되었음을 알 수 있습니다.