버블 소트 알고리즘을 다음과 같이 C++로 작성했다.
bool changed = false;
for (int i=1; i<=N+1; i++) {
changed = false;
for (int j=1; j<=N-i; j++) {
if (A[j] > A[j+1]) {
changed = true;
swap(A[j], A[j+1]);
}
}
if (changed == false) {
cout << i << '\n';
break;
}
}
위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
정답을 출력한다.
버블 정렬의 swap이 한 번도 일어나지 않는 루프가 언제인지 알아내야 한다. 버블 정렬에서 swap이 일어나지 않았다는 것은 이미 정렬되었다는 것을 의미한다. for문 내에서 index는 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. swap을 통해 왼쪽으로 이동할 수 있는 최대 거리는 루프 내에서 1이라는 것을 의미한다. 따라서 데이터 정렬 전과 후의 인덱스를 비교해 정답을 구할 수 있다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
final int N = Integer.parseInt(br.readLine()); // 데이터 개수
mData[] data = new mData[N];
for(int i = 0; i < N; i++)
data[i] = new mData(i, Integer.parseInt(br.readLine()));
Arrays.sort(data);
int max = -1;
for(int i = 0; i < N; i++) {
max = Math.max(max, data[i].index - i);
}
bw.write(String.valueOf(max + 1));
bw.flush();
bw.close();
}
}
class mData implements Comparable<mData>{
int index;
int value;
public mData(int index, int value) {
super();
this.index = index;
this.value = value;
}
@Override
public int compareTo(mData o) {
if(this.value > o.value)
return 1;
else if(this.value < o.value)
return -1;
return 0;
}
}