삽입 정렬 시간 재기

문제 정보

문제

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽입 정렬의 구현은 다음과 같습니다.

void insertionSort(vector<int>& A) {
  for(int i = 0; i < A.size(); ++i) {
    // A[0..i-1] 에 A[i] 를 끼워넣는다
    int j = i;
    while(j > 0 && A[j-1] > A[j]) {
      // 불변식 a: A[j+1..i] 의 모든 원소는 A[j] 보다 크다.
      // 불변식 b: A[0..i] 구간은 A[j] 를 제외하면 정렬되어 있다.
      swap(A[j-1], A[j]);
      --j;
    }
  }
}

삽입 정렬은 A[0..i-1] 이 정렬된 배열일 때, A[i] 를 적절한 위치를 만날 때까지 왼쪽으로 한칸씩 움직입니다. 예를 들어 A={5,1,4,3,2} 의 삽입 정렬은 다음과 같이 이루어집니다.

A 비고
5 1 4 3 2 초기 상태
1 5 4 3 2 1을 왼쪽으로 1칸 옮김
1 4 5 3 2 4를 왼쪽으로 1칸 옮김
1 3 4 5 2 3을 왼쪽으로 2칸 옮김
1 2 3 4 5 2를 왼쪽으로 3칸 옮김

길이 N 인 수열 A[] 가 주어집니다. 이 정렬 과정에서 숫자들을 총 몇 번이나 옮기는지를 계산하는 프로그램을 작성하세요. 예를 들어 위 배열의 경우 총 1+1+2+3=7 번 숫자를 옮기게 됩니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원 배열의 길이 N (1 <= N <= 50000) 이 주어집니다. 그 다음 줄에 N개의 정수로 A의 원소 Ai가 주어집니다. (0 <= Ai < 1,000,000)

입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

출력

각 테스트 케이스마다 한 줄에 A를 삽입정렬하는 과정에서 숫자를 옮기는 총 횟수를 출력합니다.

예제 입력

2
5
5 1 4 3 2
10
7 8 6 6 1 9 4 4 3 10

예제 출력

7
25

노트

7개의 댓글이 있습니다.