[HackerRank_C] Insertion Sort - Part 1

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

- 문제

Insertion Sort - Part 1 | HackerRank

정렬된 리스트에 새로운 값을 오른쪽에 넣는다 하였을 때 올바른 자리에 넣기까지의 과정을 출력하라.

예시

작동하는 원리

---

- 풀이

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

        else {
            arr[i] = compare;
            for (int j = 0; j < arr_count; j++)
                printf("%d ", arr[j]);
            printf("\n");
            break;
        }
    }
}

 

1. 비교할 값(맨 오른쪽 값)을 compare에 저장한다.
2. 만약 왼쪽에 있는 값이 더 크다면 오른쪽으로 값을 밀고 배열을 프린트 한다.
3. 만약 왼쪽에 있는 값이 더 작다면 해당 자리에 compare를 저장하고 배열을 프린트 한다. 삽입할 자리를 찾았으므로 break를 통해 탈출한다.

---

- 실행결과

통과!