레이팅 미적용농장 너머의 장기적인 진로 가능성을 염두에 두고, 소 베시는 여러 온라인 코딩 사이트에서 알고리즘을 배우기 시작했다.
지금까지 베시가 가장 좋아하는 알고리즘은 "버블 정렬"이다. 다음은 길이 \(N\)의 배열 \(A\)를 정렬하는, 소 코드로 작성한 베시의 초기 구현이다.
sorted = false
while (not sorted):
sorted = true
moo
for i = 0 to N-2:
if A[i+1] < A[i]:
swap A[i], A[i+1]
sorted = false
소 코드의 "moo" 명령은 "moo"를 출력하는 것 외에는 아무 일도 하지 않는 듯하다. 이상하게도 베시는 코드 곳곳에 이 명령을 넣겠다고 고집하는 것 같다.
여러 배열로 코드를 테스트하던 베시는 흥미로운 사실을 발견했다. 큰 원소들은 배열의 끝으로 매우 빠르게 끌려가는 반면, 작은 원소들이 배열의 앞으로 "거품처럼 떠오르는" 데는 매우 오랜 시간이 걸릴 수 있다는 것이다(베시는 이것이 이 알고리즘 이름의 유래일 것이라고 추측한다). 이 문제를 완화해 보고자 베시는, 메인 루프의 각 반복에서 앞으로 훑은 다음 다시 뒤로 훑도록 코드를 수정하여, 큰 원소와 작은 원소 모두 메인 루프의 각 반복에서 먼 거리를 이동할 기회를 갖도록 했다. 이제 코드는 다음과 같다.
sorted = false
while (not sorted):
sorted = true
moo
for i = 0 to N-2:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = N-2 downto 0:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = 0 to N-2:
if A[i+1] < A[i]:
sorted = false
입력 배열이 주어졌을 때, 베시의 수정된 코드가 "moo"를 몇 번 출력할지 예측해 보자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 100,000\))이 주어진다. 다음 \(N\)개의 줄에는 \(A[0] \ldots A[N-1]\)이 주어지며, 각각 \(0 \ldots 10^9\) 범위의 정수이다. 입력 원소들이 서로 다르다는 보장은 없다.
"moo"가 출력되는 횟수를 출력한다.
sort.in · 출력을 쓸 파일 sort.out5
1
8
5
3
22