[CS] 배열에서 두번째로 작은 수를 구하기

주어진 integer array에서 두번째로 작은 수(second smallest)를 구하여 보자. 일단 n개의 원소를 가진 정렬되지 않은 배열에서 가장 작은 값을 찾기 위해서는 n개 모두를 한 번은 살펴보아야 한다. O(n). 단순 무식한 방법으로 n개를 모두 살펴보면서 가장 큰 수를 찾아 제거하고, 다시 한 번 n-1를 찾아서 가장 큰 수를 출력하면 된다. 전체를 정렬하고 찾으려면 O(nlgn)이 들기 때문에 오히려 더 비효율적이다. (comparison based sort - 비교 기반 정렬)

배열의 원소가 적어도 2개 이상이라는 전제 하에, 아래 소스는 모든 원소를 두 번 읽지는 않고 한 번만 읽고 두번째로 작은 원소를 출력한다. 다만, 두번째로 작은 수가 아니라 임의의 i번째의 경우 이 방법은 사용할 수 없다. 이럴 경우에는 randomized selection을 써야 O(n)에 가능하다.

#include <iostream>

using namespace std;

main() {
	int a[] = {3, 1, 10, 34, 5, 3};
	int len = sizeof(a)/sizeof(int);
	
	for (int i = 1; i < len; i++) {
		if (a[i] <= a[0]) {
			a[1] = a[0];
			a[0] = a[i];
		} else if (a[i] < a[1]) {
			a[1] = a[i];
		}
	}
	
	cout << a[1] << endl;
}

그런데, 뭔가 더 좋은 방법이 있지 않을까?