수안이의 컴퓨터 연구실

원본 : http://www.debuglab.com/knowledge/sort.html

1.요약

C++에서는 각각 O(N*LogN), O(LogN)의 시간복잡도를 갖는 정렬, 탐색 함수를 지원합니다. O(N*LogN) 이라면 빠르다고 소문난 그 퀵정렬과 같은 것이며 O(LogN)이라면 역시나 빠르다고 소문난 이진 탐 색과 같은 것입니다.

STL(Standard Template Library)에서 알고리즘 관련 함수를 모아둔 곳에 있습니다. 빈약한 문서로 인해서 일반인이 사용하기에 무리가 있는 게 사실이지만 알고보면 어렵지 않습니다.


2.본문

주의 : 앞으로의 예제는 Visual C++ 6.0에서 간단한 Windows Application을 생성하신 후에 코드를 복사하시면 됩니다.

= 1. int의 배열을 정렬 검색해 봅시다 =

[예제1 - int 배열 정렬및 검색]

#include "stdafx.h" 

#include <algorithm> 

using namespace std; 



int APIENTRY WinMain(HINSTANCE hInstance, 

                     HINSTANCE hPrevInstance, 

                     LPSTR     lpCmdLine, 

                     int       nCmdShow) 

{ 

int ints[4] = { 3, 5, 7, 1}; 



sort( ints, ints + 4); 



bool bExist = binary_search( ints, ints + 4, 7); 



return 0; 

} 

[예제1 설명]

#include <algorithm> 

using namespace std; 

sort(), binary_search()를 사용하기 위해서 필요한 헤더를 포함시켰습니다.

namespace std;라는 선언을 해두면 함수 사용시 std::sort() 대신에 sort()라고 쓸 수 있습니다.

STL은 std라는 namespace안에서 정의되기 때문입니다.

--------------------------------------------------

int ints[4] = { 3, 5, 7, 1}; 



sort( ints, ints + 4); 

배열을 잡고 정렬시켰습니다. 정렬시킬 원소의 처음 그리고 마지막을 넘어선 곳의 주소값을 넣어주 었다는 점만 기억하시면 되겠죠.

직접 예제를 실행시켜 보시는 경우라면 디버거를 통해서 결과를 확인하시기 바랍니다. 예제를 최대 한 간단하게 하려고 했거든요.

---------------------------------------------------

bool bExist = binary_search( ints, ints + 4, 7); 

이진 탐색으로 7이 있는지 여부를 조사하고 있습니다.

---------------------------------------------------

= 2. 내 클래스의 배열을 정렬 검색해 봅시다 =

첫번째 예제는 간단히 int 형의 값을 사용했는데, 이번에는 내 클래스를 정렬하는 법을 알아보겠습니다.

[예제2 - MyInt 클래스의 배열 정렬및 검색]

// CPPSort.cpp : Defines the entry point for the application. 

// 



#include "stdafx.h" 

#include <algorithm> 

using namespace std; 



class MyInt 

{ 

public: 

MyInt(int i) : n(i) {} 

int n; 

bool operator<(const MyInt& r) const { return n < r.n ? true : false;} 

}; 



int APIENTRY WinMain(HINSTANCE hInstance, 

                     HINSTANCE hPrevInstance, 

                     LPSTR     lpCmdLine, 

                     int       nCmdShow) 

{ 

MyInt ints[4] = { 3, 5, 7, 1}; 



sort( ints, ints + 4); 



bool bExist = binary_search( ints, ints + 4, MyInt(7)); 



return 0; 

} 

[예제2 설명]

class MyInt 

{ 

public: 

MyInt(int i) : n(i) {} 

int n; 

bool operator<(const MyInt& r) const { return n < r.n ? true : false;} 

}; 

클래스 설계시 반드시 제공되어야만 하는 메소드가 있습니다. operator<() 인데요, 그래야지 sort()함수가 우리의 클래스를 가지고 비교연산을 할 수 있겠죠.

그 밖에는 특별히 해주어야 할 것은 없습니다. 여기서는 간단히 하기위해 정수 하나를 멤버로 사용했지만, 심볼테이블의 경우에는 문자열을 비교의 대상으로 삼아도 좋겠죠.

-----------------------------------------------------------

MyInt ints[4] = { 3, 5, 7, 1}; 

sort( ints, ints + 4); 

배열을 선언하고 정렬을 했습니다. 이전과의 차이점은 배열의 타입 밖에는 없습니다.

-----------------------------------------------------------

bool bExist = binary_search( ints, ints + 4, MyInt(7)); 

검색했습니다. 이전과의 차이점은 마지막 인자 7을 형변환 시켜준 것 밖에 없습니다.

-----------------------------------------------------------

- 여기서 잠깐 -

MyInt 클래스는 MyInt(int i) 생성자를 가지고 있습니다. 그러므로 컴파일러는 자동으 로 7을 MyInt로 형변환 시켜줄텐데 왜 굳이 형변환 시켜주었냐고 질문하고 싶은 분이 계신가요?

이유는 binary_search() 가 템플릿 함수이기 때문입니다. 템플릿 함수의 몸체는 우리가 함수를 어떻게 사용하는가에 따라서 생성됩니다. 다시 말해 우리가 함수의 원형에 맞춰서 함수를 사용하는 것이 아니라 우리가 사용하는 데로 함수의 원형이 결정된다는 의미입니다.

-----------------------------------------------------------

= 3. 탐색된 위치를 알아내자 =

눈치가 빠르신 분을 이미 아셨겠지만, binary_search()는 원소의 존재유무만 가르쳐 줄 뿐 그곳의 위치는 가르쳐주고 있지 않습니다. 저의 짧은 실력으로 관련문서를 뒤적거려 본 결과 find() 라는 함수가 있기는 한데 선형검색을 사용하고 있었습니다.

그래서 bianry_search()의 소스를 조금 고쳐서 발견한 위치를 반환하는 함수를 만들어 보겠습니다

[binary_search() 의 원본]

template<class _FI, class _Ty> inline 

bool binary_search(_FI _F, _FI _L, const _Ty& _V) 

{_FI _I = lower_bound(_F, _L, _V); 

return (_I != _L && !(_V < *_I)); } 

[새로 만든 MyBSearch()]

template<class _FI, class _Ty> inline 

_FI MyBSearch(_FI _F, _FI _L, const _Ty& _V) 

{_FI _I = lower_bound(_F, _L, _V); 

if(_I != _L && !(_V < *_I) ) 

return _I; 

return NULL; 

} 

-------------------------------------------------------------

밑부분이 조금 변했죠? 발견한 경우에는 _I를 반환하고 아닌 경우에는 NULL을 반환하도록

[예제 3 - 탐색된 위치를 반환하자 ]

// CPPSort.cpp : Defines the entry point for the application. 

// 



#include "stdafx.h" 

#include <algorithm> 

using namespace std; 



class MyInt 

{ 

public: 

MyInt(int i) : n(i) {} 

int n; 

bool operator<(const MyInt& r) const { return n < r.n ? true : false;} 

}; 



template<class _FI, class _Ty> inline 

_FI MyBSearch(_FI _F, _FI _L, const _Ty& _V) 

{_FI _I = lower_bound(_F, _L, _V); 

if(_I != _L && !(_V < *_I) ) 

return _I; 

return NULL; 

} 



int APIENTRY WinMain(HINSTANCE hInstance, 

                     HINSTANCE hPrevInstance, 

                     LPSTR     lpCmdLine, 

                     int       nCmdShow) 

{ 

MyInt ints[4] = { 3, 5, 7, 1}; 



sort( ints, ints + 4); 



MyInt* p = MyBSearch( ints, ints+4, MyInt(7)); 



return 0; 

} 

[예제 3 설명]

MyInt* p = MyBSearch( ints, ints+4, MyInt(7)); 

딱 한 줄 바뀌었습니다. 좀 전에 만든 MyBSearch()를 사용하도록 말이죠.

---------------------------------------------------------

= 4. 이것이 마지막이 아니지만 =

여기서는 계속 배열을 예제로 다루었지만, 실제 sort()나 binary_search() 함수는 vector나 linked list 등의 추상자료형을 상대로 사용할 수 있도록 만들어졌습니다.

또한 이 말은 위의 MyBSearch() 함수에서 NULL을 반환하는 것은 에러의 소지가 있다는 점을 얘기해 주고 있습니다.

더 이상의 설명이 이 글을 보시는 분의 머리를 얼마나 아프게 할 지 알고 있기 때문에 오늘은 이 쯤에서 줄이고 시간이 허락하는대로 이쁜 예제들을 선보이겠습니다.

마지막으로 The Practice of Programming 에 나온 말을 그대로 써드리죠.

Over the years, binary search has proven surprisingly hard for programmers to get right.
->수년 동안의 경험에 의하면, 놀랍게도 이진 탐색은 프로그래머들이 정확히 사용하기에 어려운 것으로 판명되었다.

저자는 라이브러리를 쓰는 것이 훨씬 현명하다는 말을 하려고 한 겁니다. 물론 C에서 제공되는 qsort와 bsearch를 두고 한 말이죠.

아.. 이 두 함수가 뭐냐면 C에서 지원하는 퀵정렬과 이진탐색입니다. 팁으로 다루려고 했는데 MSDN에 예제가 너무 잘나와서 차마 할 수가 없었습니다.

아.. 그리고 저자가 뭐하는 사람이냐면 브라이언 커니건이랍니다. C를 만들었다나..


3.예제



4.참고

MSDN
The Practice of Programming
The C++ Programming Laguage 3rd Edition.


- 2001.08.19 Smile Seo -