[HackerRank(C)] Sorting : Insertion Sort - Part 1

문제 링크

Insertion Sort - Part 1 | HackerRank

Algorithm > sorting > Insertion Sort

 

n이 5이면 배열은 5만큼 입력받는다. arr[1,2,4,5,3]이 입력으로 들어왔을 때, 가장 오른쪽에 있는 arr[4] = 3을 왼쪽값과 비교하면서 오름차순으로 정렬되도록 위치시키면 된다. 

arr[3] > arr[4] = 3 이므로 arr[4]는 arr[3]

arr[2] > 3 이므로 arr[3] = arr[2]

arr[1] < 3 이므로 arr[2] = 3 

 

 

코드

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

지금 생각하니까 n을 활용하지 못하고 의도와 다르게 푼 것 같다. n을 그대로 사용하면서 푼 코드를 밑에 첨부한다.

 

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

두 코드 모두 제출에 성공했다.

right라는 이름의 변수를 하나 선언해 배열의 가장 오른쪽 값을 넣어주었다. right는 인덱스 n-2부터 0까지 비교할 것이므로 for문을 arr_count-1만큼(right는 자기 자신과 비교하지 않으므로) 돌린다. arr[n-2]가 right보다 크면 arr[n-1]에 그 값을 저장한다. 이런 식으로 저장하다가 right가 더 크다면 arr[i]에 그 값을 저장하고 for문을 끝낸다. 처음에 break;를 스지 않아 틀렸다. right가 제 자리를 찾았으면 더이상 반복문을 돌릴 필요가 없으므로 break;를 써주어야 한다.