[HackerRank_C] Insertion Sort - Part 2

자료구조 복습용 sorting 문제입니다.

- 문제

www.hackerrank.com/challenges/insertionsort2/problem

Insertion Sort - Part 2 | HackerRank

첫번째 원소가 정렬되어있다 가정하고 두번째 원소부터 삽입 정렬을 반복 후, 올바른 위치에 삽입될 때마다 배열을 인쇄한다.

예시

작동하는 원리

---

- 풀이

// Complete the insertionSort2 function below.
void insertionSort2(int n, int arr_count, int* arr) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        for (int j = i; j >= 0; j--) {
            if (arr[j - 1] > key)
                arr[j] = arr[j - 1];
            else {
                arr[j] = key;            
                for (int k = 0; k < arr_count; k++)
                    printf("%d ", arr[k]);
                printf("\n");
                break;
            }
        }
    }
}

 

1. 비교할 값( i = 1~n-1)을 key에 저장한다.
2. j - 1번째 자리부터 0번째 자리까지 만약 왼쪽에 있는 값이 더 크다면 오른쪽으로 값을 밀어낸다.
3. 만약 왼쪽에 있는 값이 더 작다면 j번째 자리에 key 값으르 저장하고 배열을 프린트한다. 삽입할 자리를 찾았으므로 j for문을 탈출한다.

---

- 실행결과

통과!