[HackerRank] Sorting > Running Time of Algorithms

https://www.hackerrank.com/challenges/runningtime/problem

insertion sort로 정렬되는 동안 값이 자리가 몇 번 바뀌었는지 세는 문제다.

 

int runningTime(int arr_count, int* arr) {
    int cnt=0, 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;
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

일단 삽입정렬로 정렬해준 뒤 변수 하나만 추가해 정렬될 때 숫자가 증가되도록 하면 된다.

이중 for문을 사용하는데 첫번째 for문을 돌릴 i는 arr_count-1만큼 돌아간다. arr[i]와 arr[i+1]을 비교해 앞이 더 크면 두 번째 for문에 들어간다. arr[j]와 arr[j-1]을 비교해 오름차순으로 정렬되도록 자리를 바꿔준다. 이 때 cnt를 증가시킨다.