[HackerRank] Sorting : Find the Median

배열을 오름차순으로 정렬한 후, 가운데 값을 출력하는 문제이다.

 

void insertion_sort(int list[], int n){
    int i, j, key;
    for(i = 1; i < n; i++){
        key = list[i];
        for(j = i-1; j >= 0 && list[j] > key; j--){
            list[j+1] = list[j];
        }
        list[j+1] = key;
    }
}

int findMedian(int arr_count, int* arr) {
    insertion_sort(arr, arr_count);
    return arr[(arr_count-1)/2];
}

 

삽입정렬을 이용해 배열을 정렬하고 가운데 값을 반환해준다.

삽입정렬은 정렬된 앞부분과 자신을 비교해 자신의 위치를 찾아 삽입하는 알고리즘이다.

첫번째 자료는 이미 정렬된 상태이므로 key값은 두번째 자료부터 시작한다. 앞의 자료들과 비교해 삽입될 위치를 찾아 자료를 한 칸씩 뒤로 이동시킨다.

 

처음엔 단순히 버블정렬을 사용했다가 마지막 테스트 케이스에서 시간초과가 나서 삽입 정렬을 사용했다.

버블정렬로 풀 수 없는 문제가 많아지니 다양한 정렬 방법을 많이 알아둬야겠다.

삽입정렬 코드는 다음 링크를 참고했다.

gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html