최근 sort와 stable_sort를 써볼일이 있어서 포스팅해봅니다. 일반적으로 sort 알고리즘을 자주 쓰는데, stable_sort 라는 것도 있더군요. MSDN에 나와있는 stable_sort의 특징으로는 아래와 같습니다.
- 복잡도에 따라 많은 양의 메모리를 필요로 한다
- 최적의 상황(충분한 메모리/정렬된 원소)에서는 O(N log N)의 성능을 보여준다
- 그렇지 못한 경우에는 O( N ( log N )2 )의 성능을 보여준다
- 일반적인 경우 sort가 더 빠르다
- 정렬후 동일값의 원소 순서를 보장 해준다
sort와 stable_sort를 벤치마크한 결과를 보더라도 sort가 더 빠르다는 것을 알수 있습니다. 그렇다면 stable_sort는 언제 쓰는걸까요? sort와 stable_sort의 큰 차이점은 바로 같은 원소값의 순서를 보장해주냐 안해주냐에 있습니다. 이게 무슨 말이냐면 설명 보다 아래 코드의 결과값을 보시면 어떤 차이인지 바로 알수 있습니다.
using namespace std; class CFoo { public: CFoo(int num,const string &str) : mNum(num),mStr(str) {} void PrintFoo() { cout << mNum << "[" << mStr.c_str() << "] "; } int GetNum() const { return mNum; } private: int mNum; string mStr; }; void PrintVector(const vector<CFoo*> &vec) { for (auto it : vec) { it->PrintFoo(); } } int _tmain(int argc,_TCHAR* argv[]) { vector<CFoo*> someListForSort{ new CFoo(3, " "), new CFoo(3, " ") , new CFoo(4, " "), new CFoo(2, " ") , new CFoo(6, " "), new CFoo(3, " ") , new CFoo(5, " "), new CFoo(4, " ") , new CFoo(2, " "), new CFoo(2, " ") , new CFoo(6, " "), new CFoo(3, " ") , new CFoo(5, " "), new CFoo(4, " ") , new CFoo(2, " "), new CFoo(6, " ") , new CFoo(3, " "), new CFoo(5, " ") , new CFoo(1, "A"), new CFoo(1, "B") , new CFoo(1, "C"), new CFoo(1, "D") , new CFoo(1, "E"), new CFoo(1, "F") , new CFoo(1, "G"), new CFoo(1, "H") , new CFoo(1, "I"), new CFoo(1, "J") , new CFoo(4, " "), new CFoo(2, " ") , new CFoo(6, " "), new CFoo(3, " ") , new CFoo(5, " "), new CFoo(4, " ") , new CFoo(2, " "), new CFoo(6, " ") , new CFoo(3, " "), new CFoo(5, " ") , new CFoo(4, " "), new CFoo(2, " ") , new CFoo(2, " "), new CFoo(6, " ") , new CFoo(3, " "), new CFoo(5, " ") , new CFoo(4, " "), new CFoo(2, " ") }; vector<CFoo*> someListForStableSort(someListForSort); // Sort cout << "Before Sort" << endl; PrintVector(someListForSort); cout << endl; sort(someListForSort.begin(), someListForSort.end(), [](const CFoo* lhs, const CFoo* rhs)->bool { if (lhs->GetNum() > rhs->GetNum()) return true; return false; }); cout << "Aftere Sort" << endl; PrintVector(someListForSort); cout << endl; cout << endl; // Stable Sort cout << "Before stable_sort" << endl; PrintVector(someListForStableSort); cout << endl; stable_sort(someListForStableSort.begin(), someListForStableSort.end(), [](const CFoo* lhs, const CFoo* rhs)->bool { if (lhs->GetNum() > rhs->GetNum()) return true; return false; }); cout << "Aftere stable_sort" << endl; PrintVector(someListForStableSort); return 0; }
결과는 아래와 같습니다.
sort로 정렬된 값을 보시면 같은 1의 값을 갖고 있는 알파벳 순서가 뒤바뀐것을 확인할 수 있습니다. 그에 반해 stable_sort는 알파벳 순서가 변하지 않은 것을 확인할 수 있습니다.
참조
http://msdn.microsoft.com/ko-kr/library/z02ba27t.aspx
https://solarianprogrammer.com/2012/10/24/cpp-11-sort-benchmark/
반응형
'프로그래밍' 카테고리의 다른 글
C# Boxing과 Unboxing (1) | 2015.01.30 |
---|---|
Unity Cloud Data 소개 (3) | 2015.01.15 |
C# ASP.NET MVC4 핫링크 방지 ( Hotlink Protection ) (1) | 2014.06.15 |
C# Mock을 이용한 테스트 환경 조성 (2) | 2014.05.18 |
[KGC13] 쿠킹스타 제작 사례로 보는 cocos2d-x 소개 (0) | 2014.03.05 |