레이팅 미적용농장 너머의 장기적인 진로 가능성을 염두에 두고, 소 베시는 여러 온라인 코딩 사이트에서 알고리즘을 배우기 시작했다. 베시가 가장 좋아하는 두 알고리즘은 "버블 정렬"과 "퀵 정렬"인데, 안타깝게도 베시는 이 둘을 쉽게 혼동해서 결국 둘의 다소 이상한 혼합물을 구현하고 만다!
배열 \(A\)에서 원소 \(i\)와 \(i+1\) 사이의 위치를, \(A[...i]\)의 최댓값이 \(A[i+1 \ldots]\)의 최솟값 이하일 때 "분할점"이라고 부르자. 베시는 퀵 정렬이 배열을 재배열하여 분할점을 만든 다음 양쪽 \(A[...i]\)와 \(A[i+1 \ldots]\)을 재귀적으로 정렬하는 것임을 기억하고 있다. 하지만 배열의 모든 분할점을 선형 시간에 찾을 수 있다는 것은 (정확하게) 기억해 내면서도, 퀵 정렬이 분할점을 빠르게 만들기 위해 배열을 어떻게 재배열해야 했는지는 잊어버렸다! 정렬 알고리즘 역사상 최악의 알고리즘 실수가 될지도 모를 결정으로, 베시는 안타깝게도 이 작업에 버블 정렬을 사용하기로 한다.
다음은 배열 \(A\)를 정렬하는 베시의 초기 구현 개요이다. 먼저 버블 정렬 한 번의 패스를 수행하는 간단한 함수를 작성한다.
bubble_sort_pass (A) {
for i = 0 to length(A)-2
if A[i] > A[i+1], swap A[i] and A[i+1]
}
그다음 퀵(비슷한) 정렬 함수의 재귀 코드는 다음과 같이 구성된다.
quickish_sort (A) {
if length(A) = 1, return
do { // Main loop
work_counter = work_counter + length(A)
bubble_sort_pass(A)
} while (no partition points exist in A)
divide A at all partition points; recursively quickish_sort each piece
}
베시는 자신의 코드가 얼마나 빨리 실행될지 궁금하다. 간단히 하기 위해, 베시는 메인 루프의 각 반복이 선형 시간이 걸린다고 보고, 알고리즘이 수행한 총 작업량을 추적할 수 있도록 루프 안에서 work_counter라는 전역 변수를 그에 맞게 증가시킨다.
입력 배열이 주어졌을 때, 이 배열에 quickish_sort를 적용한 뒤 work_counter의 최종 값을 예측해 보자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 100,000\))이 주어진다. 다음 \(N\)개의 줄에는 \(A[0] \ldots A[N-1]\)이 주어지며, 각각 \(0 \ldots 10^9\) 범위의 정수이다. 입력 원소들이 서로 다르다는 보장은 없다.
work_counter의 최종 값을 출력한다.
sort.in · 출력을 쓸 파일 sort.out7
20
2
3
4
9
8
712In this example, we start with the array 20 2 3 4 9 8 7. After one pass of
bubble sort (adding 7 to the work counter), we get 2 | 3 | 4 | 9 8 7 | 20, where |
denotes a partition point. Our problem is therefore divided into recursive
subproblems involving sorting 2, 3, 4, and 20 (each taking zero
units of work), and 9 8 7. For the 9 8 7 subproblem, one pass of the main loop
(3 units of work) yields 8 7 | 9, after which a final pass over 8 7 (2 units of
work) effectively finishes the sort.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Platinum