삽입정렬

void selection_sort(int * arr, int len) //오름차순
{
    for (int i = 1; i < len; i++)
    {
        int j;
        int val = arr[i];
        
        for (j = i - 1; j >= 0; j--)
        {
            if (val < arr[j])
            	arr[j + 1] = arr[j];
            else
            	break;
        }
        arr[j + 1] = val;
   }
}

시간복잡도가 O(n^2) 인 정렬 알고리즘 중 하나이다.

이미 정렬된 경우 O(1)의 성능을 보인다.

 

5, 4, 1, 2, 3 이 함수의 인자로 전달 되면

0번 인덱스는 이미 정렬되어 있다고 가정하면서 정렬을 시작한다.

 

1) 5 | 4, 1, 2, 3 에서 4를 선택한다. j = 0 이므로 아래 반복문을 시작한다. arr[1] = arr[0] 을 대입한다. 반복문을 탈출한다. arr[0] = val, 4를 대입한다. -> 4, 5 | 1, 2, 3

 

2) 4, 5 | 1, 2, 3 에서 1을 선택한다. j = 1 이므로 아래 반복문을 시작한다. 1 < 5 이므로 arr[2] = arr[1] 을 대입한다. 

1 < 4 이므로 arr[1] = arr[0]을 대입한다. 이제 반복문을 탈출한다. arr[0] = val, 1을 대입한다. 

-> 1, 4, 5 | 2, 3

 

3) 1, 4, 5 | 2, 3 에서 2를 선택한다. j = 2 이다. 2 < 5이므로 arr[3] = arr[2], 2 < 4  이므로 arr[2] = arr[1]

2 > 1 이므로 반복문을 탈출한다. 이 때 j는 0 이다. 그래서 arr[1] = val, 2를 대입한다.

-> 1, 2, 4, 5 | 3 

 

4) 1, 2, 4, 5 | 3 에서 3을 선택한다. j = 3 이다. ... j = 2 에서 3 > 2 이므로 반복문을 탈출한다.

arr[2] = val, 3 을 대입한다. -> 1, 2, 3, 4, 5

 

오름차순으로 정렬이 완료된다.

 

주어진 배열 내 에서 정렬을 하므로 in-place 하고,

들어 온 순서대로 정렬이 완료된다. 

3, 2, 2 가 있을 때 1번 인덱스의 2가 먼저 자리를 잡고, 2번 인덱스의 2는 등호로 인해 else 에서 빠져나오게 된다.