삽입 정렬(Insertion Sort)

Sort

• 선택 정렬(Selection Sort)
• 버블 정렬(Bubble Sort) 
• 삽입 정렬(Insertion Sort)

---

삽입 정렬(Insertion Sort)을 구현해 보았다.

void insertion_sort(int arr[], int n)
{
    int j;
    for(int i = 1 ; i < n ; i++)
    {
        int temp = arr[i];
        for(j = i-1 ; j >= 0 ; j--)
        {
            if(arr[j] > temp) arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = temp;
    }
}

우선, 자신이 삽입되어야 할 자리를 자신의 앞에서 찾기 때문에 아래의 동작을 i = 1에서부터 n-1까지 반복한다.

• temp 변수에 현재 자신의 값을 저장해둔다.
• 반복문을 사용해 자신보다 작은 값을 찾을 때 까지 자신 앞의 값들을 뒤로 한 칸씩 옮긴다.
• 자기보다 작은 값을 발견한 경우 break로 작은 값 탐색을 종료한다.
• 자기보다 작은 값 다음에 자신의 값(temp)를 대입한다.

 

Best Case	Worst Case	Average Case	Stable	Inplace
O(n)	O(n^2)	Ө(n^2)	Yes	Yes

 

---

 

선택 정렬(Selection Sort)

버블 정렬(Bubble Sort)