반응형

 예전에 네이버 블로그를 운영했을 때, 이 글에서 compare 메서드에 대해서 언급했던 적이 있었습니다. 이것에 대해서 혼동되게 설명한 것도 있고, 잘못 설명한 것도 있어서 다시 짚고 넘어가겠습니다.

 


 먼저, Comparable interface에 정의된 CompareTo 메서드에 대한 설명입니다.

 

 

 특정 object를 ordering을 위해서 비교한다고 되어 있습니다. 우선 순위가 높다. 낮다 보다는, 순서를 매기기 위해서 이 메서드를 호출한다고 보는 것이 적절해 보입니다.

 

 

 그리고 리턴 부분을 보면, -1, 0, 1이 아닌 단순히 음수, 0, 양수를 리턴한다고 되어 있습니다. -1을 리턴하는 것과 음수를 리턴하는 것은 의미상 차이가 분명히 있는 부분입니다. 아래 예제 프로그램을 보시면 명확하게 다가옵니다.

 

 

 String 3개가 있습니다. 이것은 Comparable을 구현한 클래스 입니다. x는 "a", y는 "cd", z는 "cd"입니다. 6번째 줄은 x와 y를 비교를 하고, 7번째 줄은 y와 x를 비교합니다. 다음에, 8번째 줄은 y와 z를 비교합니다.

 

 

 결과는 -2, 2, 0이 나옵니다. 이는, x가 사전순으로 y보다 앞서고, y가 x보다 사전순으로 뒤에 있기 때문입니다. 그리고, y와 z는 같은 문자열이기 때문입니다. 중요한 것은, 이 결과가 대체 어디에 어떻게 쓰이느냐는 것입니다. 객체의 상대적인 순서가 필요한 작업이 뭐가 있을까요? 정렬, priority_queue 정도가 있겠네요.

 

 


 보통, sort를 많이 하니, 아래 소스코드를 디버깅 해 보도록 하겠습니다. 그리고, 이것은 ordering을 한다고 봐도 됩니다. 순서를 어떠한 기준에 의해서, 재배치 하는 것이기 때문입니다.

 

 

 이것은 단순히, String 배열을 만들어 놓고, 정렬을 합니다. compareTo 메서드에 브레이크 포인트를 걸어놓고 보겠습니다.

 

 

 배열의 크기가 작으므로, 183번째 if문에 걸릴 겁니다. 그러므로, 184번째 줄에 있는 countRunAndMakeAscending 메서드하고 185번째 줄의 binarySort 메서드에서 해당 메소드를 호출할 겁니다.

 

 

 run을 찾는 메서드 내부를 봅시다. 여기서 주목해야 할 부분은 317번째 줄입니다. runHi에 있는 것과 runHi-1에 있는 것 둘을 비교했을 때, runHi에 있는 것이 더 작으면 계속 runHi를 증가시킨다고 되어 있습니다. 즉, 이러한 상황입니다.

 

 

 이 때 runHi가 계속 증가할 겁니다. 그러다가, a[5]하고 a[4]를 compareTo로 비교했을 때, 양수가 나오거나 0이 나오는 경우를 생각해 봅시다.

 

 

 이 경우에, runHi가 멈출 겁니다. 그 후에, a(1)부터 a(4)까지의 구간이 뒤집힙니다.

 

 

 이를 다시 바꿔 보면, 정렬에서, x.compareTo(y)의 리턴값이 음수라면, x가 y보다 앞에 온다는 의미가 됩니다. 양수라면 x가 y보다 뒤에 온다는 것이고 0이면, 어떤 정렬이냐에 따라서 앞에 오는지, 뒤에 오는지가 달라집니다.

 

 

 그리고 이 리턴값은 binarySort에서도 써먹을 수 있습니다. 비교 값을 기준으로 탐색 구간을 반씩 잘라버리는 binary sort와 같이요. start는 해당 상황에서 4를 의미합니다. 하늘색으로 칠해진 부분입니다.

 

 

 start가 hi가 될 때 까지 계속 start가 증가하는데요.

 

 258번째 줄에 보면, pivot하고, a[mid]를 비교해서, pivot이 더 작으면 right에 mid를 대입하라고 되어 있습니다. 그런데, 상대적인 크기를 보면, 군청색이 a[mid]보다는 작은 상황이므로, right가 a(2)를 가리키게 됩니다.

 

 

 탐색 구간이 반으로 줄었습니다. 이런 식으로 탐색 구간을 반씩 줄인 다음에, 넣어야 할 위치에 넣으면 되겠군요. 이진 탐색도 객체들의 order 관계를 이용해야 합니다. 순서 정도라고 이해하면 될까요? 1은 2보다 앞서야 하고, 2는 3보다 앞서야 하는 것처럼, 객체 a는 b보다는 앞서고, b는 c보다는 앞서야 한다. 이런 식의 관계라고 생각하시면 좋습니다.

 

 단지, ordering이 뭔지 모른다고 하셔도, 정렬을 하기 위해서 '정렬이 되어야 하는 순서'는 필요하고, 그것을 위해서 compareTo를 호출한다. 정도만 짚고 넘어가셔도 좋습니다.

 

 


 순서가 필요한 것 중 또 다른 하나는 우선순위 큐입니다. 위 예제를 보면, pq에 "a", "bc", "bc", "a"를 차례대로 넣고, 꺼내는 연산을 합니다.

 

 

 pq.add를 보면 siftUp이 있습니다. String은 Comparable이 있으므로, 646번째 줄에 있는 것이 호출됩니다. 또한, 643번째 줄의 파라미터 x는 새로 추가하는 원소임을 파악할 수 있습니다. 아시다시피, Heap에 추각할 때에는 추가하는 원소를 계속 Up을 시키는 식으로 동작합니다.

 

 

 그러면, 언제 계속 올라가는지 보면 될 건데요. 652번째 줄에 key 값에다가 x를 넣음을 알 수 있습니다. 즉, key는 힙에 새로 추가하는 객체입니다. 다음에, e는 parent를 의미하는데요. key.compareTo(e)가 음수라면 계속 타고 올라갈 겁니다.

 

 

 그림으로 그려보면 이런 경우일 겁니다. 이 때, key.compareTo(queue[parent])의 리턴값이 0보다 작은 음수가 되므로, 주황색으로 표시된 v는 밑으로 내려오게 됩니다.

 

 

 그리고 키값은 k의 부모 위치에 있는 원소와 비교하게 될 겁니다. 여기에서도 중요한 것은 우선 순위큐도, 순서가 중요하다는 것입니다. 실행 결과는 아래와 같습니다.

 

 

 여기서 중요한 것은 딱 2개입니다. x.compareTo(y)는 x와 y를 비교해서 순서 관계를 음수, 0, 양수 중 하나로 리턴합니다. 이 관계는 정렬, 우선순위 큐, TreeMap, TreeSet 같이 order가 중요한 곳에서 씁니다. 이 두 개만 짚고 넘어가셔도 무난할 듯 싶습니다.

반응형

댓글을 달아 주세요