삽입 정렬 시간 재기
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- MEASURETIME
- 2000ms
- 65536kb
- 2243
- 775 (34%)
-
- 출처
- 분류
문제
유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 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
노트