꽃미남 프로그래머 김포프가 창립한 탑 프로그래머 양성 교육 기관 POCU 아카데미 오픈!
절찬리에 수강생 모집 중!
프로그래밍 언어 입문서가 아닌 프로그래밍 기초 개념 입문서
문과생, 비전공자를 위한 프로그래밍 입문책입니다.
jobGuid 꽃미남 프로그래머 "Pope Kim"님의 이론이나 수학에 치우치지 않고 실무에 곧바로 쓸 수 있는 실용적인 셰이더 프로그래밍 입문서 #겁나친절 jobGuid "1판의내용"에 "새로바뀐북미게임업계분위기"와 "비자관련정보", "1판을 기반으로 북미취업에 성공하신 분들의 생생한 경험담"을 담았습니다.

sort와 stable_sort

프로그래밍 2014. 12. 25. 18:58
Posted by 친절한티스

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

댓글을 달아 주세요