U E D R , A S I H C RSS

STL/sort

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
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:27:58
Processing time 0.0095 sec