sort ¶
- 우리는 프로그램 첨 배울때 sort 짜는걸 많이 한다. 수행시간이 θ(n*n)이나 되는 소트를 짜곤 했다.
- STL에서는 Quick Sort를 약간 변형한 Sort 알고리즘을 제공한다.
- 예제를 보자.
~cpp #include <iostream> #include <vector> #include <algorithm> // sort 알고리즘 쓰기 위한것 #include <functional> // less, greater 쓰기 위한것 using namespace std; typedef vector<int>::iterator VIIT; int main() { int ar[10] = {45,12,76,43,75,32,85,32,19,98}; vector<int> v(&ar[0], &ar[10]); sort(v.begin(), v.end(), less<int>()); // 오름차순 for(VIIT it = v.begin() ; it != v.end(); ++it) cout << *it << endl; cout << endl; sort(v.begin(), v.end(), greater<int>()); // 내림차순 for(VIIT it = v.begin() ; it != v.end(); ++it) cout << *it << endl; // 간단하게 오름차순 쓸거면 <functional> 없애고 sort(v.begin(), v.end()) 하면 된다. return 0; }
- STL의 이런 편리함은 프로그래머가 자료구조 만드느라 애쓰는 시간을 알고리즘을 생각하는 시간으로 돌려준다.
- 한가지 주의할점. 이 sort알고리즘은 컨테이너가 임의 접근(Random Access)을 허용한다는 가정하에 만든것이다. vector나 deque처럼 임의 접근을 허용하는 컨테이너는 이걸 쓸수 있지만. list는 임의 접근이 불가능해서 사용할수 없다. -l5 이런 접근이 안된다는 의미 - 따라서 list에서는 컨테이너 내부에서 sort메소드를 제공해 준다.
STL