[알고리즘] 정렬3: Insertion sort

Insertion Sort

: 삽입 정렬은 왼쪽 부터 항을 1개씩 정렬해나가면서 하나씩 항목을 추가해가면서 뒤에서부터 삽입해서 정렬되는 위치까지 삽입시키는 알고리즘이다.

--> 루프0
index 1을 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 0과 비교하여 작으면 위치를 바꾼다.
index 1까지 정렬 완료
--> 루프 1
index 2를 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 1과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 0과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 2까지 정렬 완료
--> 루프2
index 3를 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 2과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 1과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 0과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 3까지 정렬 완료
...

ex)
loop i=1, j=0 ; index 1의 위치 찾기.
5 1 9 3 4 : index 1을 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 5 9 3 4 : 결과

loop i=2, j=1~0 ; index2의 위치 찾기
1 5 9 3 4 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break

loop i=3, j=2~0 ; index 3의 위치 찾기
1 5 9 3 4 : index 3를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 5 3 9 4 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 5 9 4 : index 1를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break
1 3 5 9 4 : 결과

loop i=4, j=3~0 ; index 4의 위치찾기
1 3 5 9 4 : index 4를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 5 4 9 : index 3를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 4 5 9 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break
1 3 4 5 9 : 결과
끝

void insertion_sort(int arr[], int size) {
    for(int i = 1 ; i <= size - 1 ; i++) 
        for (int j = i-1 ; j >= 0 ; j--) 
            if(arr[j] > arr[j+1]) {
                // swap(arr[j], arr[j+1]);
                int t = arr[j] ;
                arr[j] = arr[j+1] ;
                arr[j+1] = t ;
            } 
            else
                continue;
}