C++ 정렬 - 정렬 기준

먼저, 기본적인 C++ 표준 라이브러리 sort 함수의 동작에 관해서는 이 글을 참고.

이번 글은 (앞 글과 비슷한) sort 함수를 이용하는 간단한 예제로 시작하려 한다:

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  const unsigned size = 9;
  string a[size] = {"Rammus", "Lucian", "Kennen", "Darius", "Anivia",
                    "Ezreal", "Aatrox", "Graves", "Draven"};

  sort(a, a + size);

  for (unsigned i = 0; i < size; ++i)
    cout << a[i] << '\n';

  return 0;
}

이전 예제와 다른 점은 array (a[]) 가, int가 아닌, string을 저장한다는 점이다.
(sort 함수를 처음 이용하시는 분들은 #include <algorithm>과 sort()부분들에 주목!)

여기에서 궁금한 점이 생길 것이다. (아니, 생겨야 한다. ㅎㅎ)
int나 string 같은 건 정렬 방법이 자명하니까 sort 함수가 처리할 수있다고 하자.
그런데, 정렬 방법이 불투명한 자료형을 저장하는 array는, sort 함수가 어떻게 처리할까?

다음 예시를 보자:

#include <algorithm>
#include <iostream>

using namespace std;

class champion {
  public:
   champion(const char *_name, unsigned _hp) {
     name = string(_name);
     hp = _hp;
   }   

   string name;
   unsigned hp; 
};

int main() {
  const unsigned size = 9;
  champion a[size] = {champion("Rammus", 420), champion("Lucian", 390),
                      champion("Kennen", 403), champion("Darius", 426),
                      champion("Anivia", 350), champion("Ezreal", 350),
                      champion("Aatrox", 395), champion("Graves", 410),
                      champion("Draven", 420)};

  sort(a, a + size);

  for (unsigned i = 0; i < size; ++i)
    cout << a[i].name << ' ' << a[i].hp << '\n';

  return 0;
}

위의 코드에서 특이 사항은, champion이라는 자료형을 정의하고, array가 그 자료형의 자료들을 저장하게 했다는 점이다.
sort함수가 어떻게 동작할까?
답은, "동작 안 한다." 이다.
아니, 더 정확하게 이야기하면, 컴파일 자체가 안 된다.
(다음과 같은 쳐다보기도 싫은 에러 메시지가 뜬다.):

In file included from /usr/include/c++/4.6/algorithm:63:0,
                 from main.cpp:1:
/usr/include/c++/4.6/bits/stl_algo.h: In function ??void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = champion*]??:
/usr/include/c++/4.6/bits/stl_algo.h:2181:4:   instantiated from ??void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = champion*]??
/usr/include/c++/4.6/bits/stl_algo.h:5409:4:   instantiated from ??void std::sort(_RAIter, _RAIter) [with _RAIter = champion*]??
...

즉, sort 함수는, 어떻게 정렬할 지 모르겠으면, 걍 안 한다.
그럼 어떻게 해야 sort 함수가 동작 할까?

일단은 sort 함수에, "어떻게 정렬해야 한다" 라는 방법을 (즉, 정렬 기준을) 넘겨줘야겠지?
아래 코드의 ... 부분에 그 정렬 기준을 넘겨줄 것이다:

sort(a, a + size, ...)

이를 위해, 정렬 기준은 함수로 나타낼 것이고, 그 함수를 (더 정확히는 그 함수를 가리키는 포인터를) 위에 보인 자리에 (... 부분에) 넘겨줄 것이다.
예를 들어, hp 순서대로 정렬하려 한다면, 일단 다음과 같이 정렬 방법을 함수로 나타내야 한다. (main 함수 앞에 넣자.):

bool compare_hp(champion e1, champion e2) {
  return e1.hp < e2.hp;
}

이 함수는 다음과 같이 동작한다:

• 일단, 두 개의 champion 형의 자료를 받는다. (e1과 e2)
• 구현할 정렬 기준 (이 예제에서는 hp의 크기) 에 대해서, e1이 e2 보다 작으면 true를 return하도록 한다.

그리고, sort 함수를 부르는 부분을 다음과 같이 고친다:

sort(a, a + size, compare_hp);

이게 바로 sort 함수에, 정렬 기준을 정의하는 함수의 포인터를 넘기는 방법이다.

이제, 프로그램을 컴파일해서 실행시키면 다음과 같이, hp로 정렬된 결과를 얻을 수있다:

Anivia 350
Ezreal 350
Lucian 390
Aatrox 395
Kennen 403
Graves 410
Rammus 420
Draven 420
Darius 426

참고로.. 전체 code는 다음과 같다:

#include <algorithm>
#include <iostream>

using namespace std;

class champion {
  public:
   champion(const char *_name, unsigned _hp) {
     name = string(_name);
     hp = _hp;
   }   

   string name;
   unsigned hp; 
};

bool compare_hp(champion e1, champion e2) {
  return e1.hp < e2.hp;
}

int main() {
  const unsigned size = 9;
  champion a[size] = {champion("Rammus", 420), champion("Lucian", 390),
                      champion("Kennen", 403), champion("Darius", 426),
                      champion("Anivia", 350), champion("Ezreal", 350),
                      champion("Aatrox", 395), champion("Graves", 410),
                      champion("Draven", 420)};

  sort(a, a + size, compare_hp);

  for (unsigned i = 0; i < size; ++i)
    cout << a[i].name << ' ' << a[i].hp << '\n';

  return 0;
}

C++ 정렬에 관한:

이전 글

다음 글 (Coming soon)