선택 정렬의 개선

데추주를 위해 선택 정렬을 짜는데 무언가 익숙함이 느껴졌다. 어 이거... RMQ?

 

RMQ는 세그먼트 트리를 이용하면 각 쿼리를 $O(logN)$에 구할 수 있음이 잘 알려져 있고, 선택 정렬을 시행할 때 필요한 쿼리의 수는 $N$번이다.

 

세그먼트 트리를 전처리하는 데에도 $O(NlogN)$이 필요하므로, 최종 시간복잡도 $O(NlogN)$에 배열을 정렬할 수 있다.

 

 

BOJ 2751에 제출해보니 메모리와 시간 면에서 그다지 효율적이지는 않아도 나름 선전하는 모습을 보여줬다.

 

위에서부터 순서대로 std::sort, quick sort, merge sort, heap sort, selection sort with segment tree 이다.

 

#include<bits/stdc++.h>
using namespace std;
#define nm (nl+nr>>1)
typedef pair<int,int> pii;
const int N = 1e6+1;
int n,a[N]; pii tree[4*N];
void init(int nl=1,int nr=n,int i=1) {
	if(nl==nr){ tree[i]={a[nl],nl}; return; }
	init(nl,nm,i<<1); init(nm+1,nr,i<<1|1);
	tree[i]=min(tree[i<<1],tree[i<<1|1]);
}
void update(int x,int v,int nl=1,int nr=n,int i=1) {
	if(nl==nr){ tree[i].first=v; return; }
	if(x<=nm) update(x,v,nl,nm,i<<1);
	else update(x,v,nm+1,nr,i<<1|1);
	tree[i]=min(tree[i<<1],tree[i<<1|1]);
}
pii query(int l,int r,int nl=1,int nr=n,int i=1) {
	if(r<nl||nr<l) return {2e9,n+1};
	if(l<=nl&&nr<=r) return tree[i];
	return min(query(l,r,nl,nm,i<<1),query(l,r,nm+1,nr,i<<1|1));
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	init();
	for(int i=1;i<n;i++){
		int j = query(i,n).second;
		swap(a[i],a[j]);
		update(i,a[i]); update(j,a[j]);
	}
	for(int i=1;i<=n;i++) cout << a[i] << ' ';
}