Heap sort (힙 정렬)

Heap sort는 root node에 항상 제일 작은 값이나 제일 큰 값이 오도록 heap tree를 구성해서 정렬하는 방법이다. Heap tree의 root에 최소 값이 오도록 구현하면 min heap tree, 최대 값이 오도록 하면 max heap tree라 한다. Heap tree를 구성하는 방법에 대해서는 별도의 포스트로 다루고 여기서는 max heap으로 오름차순 정렬하는 과정을 설명한다.

Heap sort는 한번 heap tree를 구성한 다음에는, 어떤 값이 제자리를 찾는데 소요되는 시간이 짧다는 점을 이용한다. 부모와 자식노드의 값에 따라 완전 이진트리로 구성하므로, 처음 한 번 heap tree를 구성할 때 O(N/2)만큼 소요된 이후에는, heap tree가 구성된 상태에서는 어떤 노드의 제자리를 찾는데 O(log N) 만큼이 소요된다.

Heap sort 과정을 정리하면 다음과 같다.

언뜻 잘 이해가 안 갈수도 있는데, 모종의 과정을 거치고 나면 root (배열의 0번 index)에 최대값이 오게되는 마법의 tree가 있고 이것의 root를 싹둑싹둑 자를때마다 남아있는 것들 중 제일 큰값이 root에 올라오는 것을 상상해보면 도움이 될지도 모르겠다. Tree라고 하면 일반적으로 왼쪽과 오른쪽 자식노드에 대한 pointer를 가지는 형태를 떠올리게 되니까 배열로 표현된 tree가 혼동스러울 수도 있겠는데, 완전 이진 트리인 경우에는 배열안에 원소들이 차례대로 들어 있다고 가정할 때 왼쪽/오른쪽 자식 node의 위치를 다음의 계산식으로 구할 수 있다.

그리고 하나라도 자식이 있는 부모 node들의 index도 구할 수 있다.

 

어떤 배열이 다음의 순서일 때 이를 heap sort하는 과정의 예를 들어 살펴보자.

 

1. “Heap tree를 만든다.”

Max heap을 가정하므로, 위의 배열로 max heap tree를 만들면 다음과 같다. 대괄호([ ]) 안에 있는 숫자는 배열상의  index를 의미한다.

예제의 경우, 이미 “모든 서브트리의 부모가 가진 값이 자식보다 크다”는 max heap tree 조건을 만족하기 때문에 배열 안에서의 순서가 변경되지 않는다. 다른 경우에 heap tree를 생성하는 절차는 나중에 설명하도록 하고 지금은 꼼수 같겠지만 일단 그냥 넘어가자. 위 그림에서 색칠된 node들은 자식들을 가지는 부모 node들인데, 앞서 설명한 부모 node들의 index를 구하는 공식에 의해서 얻을 수 있다. 이 예제에서는 잘 보이지 않지만, 부모 node들의 index를 구하는 것은 heap tree를 구성할 때 중요하다. 이 부분도 별도의 포스팅으로 따로 설명한다.

 

2. “제일 마지막 node를 root와 바꿔서 heap tree를 망가뜨린다.”

“아니 왜?” 하는 생각이 들 수도 있을 텐데, root에는 최대값이 들어 있으므로 제일 마지막 node와 swap하면 root에 있던 값은 오름 차순 정렬일 때의 자기 자리를 찾아가는 샘이 된다.

 

3. “Heap tree를 구성하는 배열의 크기를 하나 줄인다.”

이전의 root였던 10은 제자리를 찾았으니 이제 배열의 크기를 하나 줄여서 index 0 ~ 8까지가 배열이라고 가정한다. 배열 그림을 보면 정렬되어가는 모습이 보일 것이다.

 

4. “다시 heap tree가 되도록 새로운 root의 자리를 찾아 준다.”

얼떨결에 새로운 root가 된 node는 이제 자기 있을 곳을 찾아가야 한다. 자식 node들과의 크기를 비교해서 둘 중 큰 자식과 swap하면서 원래 있어야 할 곳을 찾아간다. 완전 이진 트리의 장점을 살려서 O(log N)의 비교 연산만에 자기 자리를 찾을 수 있다. 이 과정에서 노드들간의 swap이 일어나고 root에는 다시 최소 혹은 최대값이 오게된다.

Root였던 ‘1’은 자식들 중 더 큰 왼쪽 자식인 ‘9’와 자리를 바꾼다.

여전히 max heap tree를 만족하지 못하므로 ‘7’, ‘6’ 중 큰 자식인 ‘7’과 자리를 바꾼다.

마지막으로 ‘3’, ‘2’ 중 큰 자식인 ‘3’과 자리를 바꾸면 모든 서브트리가 max heap tree의 조건을 만족하는 상태가 된다.

 

5. “위의 2, 3, 4번 과정을 배열의 크기가 1이 될때 까지 반복한다.”

이제 다시 새로뽑힌 root와 마지막 node인 2를 swap하고 배열 크기를 하나 줄인 다음 새로운 node의 자리를 찾아준다. 즉, node를 swap하고 index를 하나 줄이는 과정을 O(N)번 반복 하고 각 반복 마다 O(log N)의 –정확히는 매 반복 마다 배열의 크기가 하나씩 줄어듬– 비교 연산이 필요하다.  한바퀴 더 돌아 보면.

바꾸고

크기줄이고

자리 찾아주고

이렇게 원소를 하나씩 줄여 가면서 1개가 남을때까지 반복하면 정렬된 배열을 얻게 된다.

Code로 나타내면 다음과 같다. (충분히 시험되지 않았음)

 

 

Fitbit Surge strap 교체기

Fitbit Surge는 아직 국내에 정식으로 들여오는 곳이 없는 모양이다. 직구로 산지 2년 정도 되었는데 벌써 strap 안쪽이 망가졌다. 시계와 줄이 일체형이어서 따로 strap을 판매 하지는 않고 보증기간 이내이면 교환해 주는게 정책이라는데 이미 날짜도 지나고 해서 자가 수리를 해보기로 했다.

  • 주의: 아래의 strap으로 교체한 후 2주간 사용해 봤는데, 꼭 맞지도 않아 헐거울 뿐더러 빨갛게 피부에 자국이 생겼다. 아무래도 아래의 것은 제질에 문제가 있는 모양이다. 자가 수리를 고려한다면 strap구매에 주의 하시길.

 

Strap 구매

역시 AliExpress는 별천지다. 오만게 다 있으니.. 좀더 싼것도 있었는데, 같이 준다는 “상품 손“이 유용할것 같아서 이걸로 주문했다. 한 가지 주의 할 점은 딱 strap만 들어있고 band loop lock과 buckle은 포함되어 있지 않아서 이전의 것을 빼서 써야 한다는 점이다. 참고로 주문으로 부터 도착까지 대략 2주 정도 걸렸다.

 

Video guides (YouTube)

의외로 YouTube에는 관련된 내용들이 많이 있다. 어떤 사람은 안테나를 무시하고 그냥 교체 하기도 하고, 어떤 사람은 접착제 없이 조립하기도 하는데 이것도 뭐.. 취향일까? 다음의 비디오는 안테나를 분리하는 부분이 포함되어 있다.

이 전에 쓰던 strap에서 buckle을 빼내는 부분이 약간 어려웠는데 이 부분은 아래의 비디오의 4:50 무렵을 참고하면 중국어를 몰라도 대충 눈치로 방법을 알 수 있다.

 

Rubber Cement(고무 시멘트)

위의 비디오에 나오는 제품이 드물긴 하지만 국내에도 수입해서 파는 곳이 있었다. G마켓은 일시 품절이고 바보사랑에는 재고가 있었다.

[Tip] WinDbg에서 경로가 다른 PDB의 source를 load하기

Windows에서 WinDbg로 디버깅할 때, PDB에 적혀있는 절대경로 때문에 다른 machine에서 빌드한 바이너리(dll/sys/exe)를 디버깅할 때는 소스가 맞지 않아 번거롭다. 이 것을 해결하는 방법으로 source indexing을 사용하라는 글이 있기는 했었는데 내가 뭐 배포정책을 바꿀만큼 힘이 있는 것도 아니고… 아주 약간(!) 지저분 하긴 하지만 Windows의 subst 명령어를 사용해서 PDB에 적힌 경로를 흉내내는 것으로 이 문제를 해결할 수 있었다.

 

PDB에 있는 절대 주소와 내 로컬 소스의 주소가 각각 다음과 같다고 가정한다.

즉, Local path의 EEE directory에 PDB path EEE가 연결되도록 만들면 된다. D:가 유효하다면 그걸 사용하면 되지만, 이 글에서는 C:만 사용가능한 상태라 가정한다.

먼저 C:에 가짜 디렉토리 ‘AAA\BBB\CCC\DDD’를 만든다. 꼭 C: 밑에 바로 만들지 않더라도 나중에 subst 명령어에서 경로 지정만 잘 해주면 된다. 상황에 따라 admin권한이 필요할 수도 있다.

Local path에 있는 EEE 디렉토리로 link를 만든다.

마지막으로 subst 명령어를 이용해서 Local에 만든 가짜 directory를 D:로 연결한다. 이때는 admin 권한으로 실행하면 안된다. 일반 권한으로 다음을 수행하자.

subst의 두번째 인자는 처음에 만든 가짜 디렉토리에 따라 필요한 경우 디렉토리명을 적어도 된다. 이제 d:로 이동해 보면 PDB와 동일하게 D:\AAA\BBB\CCC\DDD\EEE 경로가 유효한 것을 볼 수 있고, WinDbg에서 source loading도 제대로 동작한다.

 

해제

subst는 system을 reboot하면 해제된다. 필요한 경우 /d option으로 해제할 수 있다.