[HackerRank] Sorting : Insertion Sort - Part 2

문제

arr[0]과 arr[1]을 비교해 arr[0] > arr[1]이면 arr[0]이 자리를 찾아갈 때까지 왼쪽으로 이동한다.

 

왼쪽으로 이동한다는 것을 생각했으면 빨리 풀었을텐데, 이중 for문 쓰는 거에 정신이 팔려 한참 고민했다. j가 감소하는 경우를 생각하지 못하고 계속 증가하는 방향으로만 머리를 쓰니 안풀릴수밖에... 증가하는 방식으로 풀려면 매우 복잡해질 것 같다.

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

우선 배열 두 개를 비교해 줄 if문을 사용하고, 오른쪽이 왼쪽보다 작을 경우에는 오른쪽이 제 자리를 찾을 때까지 이동을 계속 해줘야하므로 for문을 하나 더 써주었다. 최대로 이동하면 오른쪽 배열의 인덱스만큼 이동하므로 j는 오른쪽 배열의 인덱스로 잡아주고 감소하는 방식을 사용한다. temp값을 이용해 두 배열의 값을 바꿔준다. 하나의 과정이 끝날 때마다 배열을 출력해준다.