sort와 stable_sort

최근 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/

http://ohyecloudy.com/pnotes/archives/294/

http://www.soen.kr/lecture/ccpp/cpp4/42-3-1.htm