수다닷컴

알고리즘 과제가 있어 하고 있는데 힘드네요.. c++로 작업을 하고 있는데요..

며칠째 이거만 잡고있지만 하나도 안되네요 다른 것도 공부할거 많은데 ㅜ.ㅡ 도와주세요..

정렬 알고리즘 두개를 구현해야 하는건데요..

하나는 자연합병 정렬알고리즘이구요.. 다른 하나는 토너먼트 정렬알고리즘입니다.

구글이나 네이버에서 참고할만한 소스를 찾아봐도 없네요.. ㅜ.ㅡ

어떤 식으로 구현을 해야할지 모르겠습니다.. 꼭 좀도와주세요..

두 알고리즘을 설명을 하자면 이렇습니다.
=======================================================================
1. 자연합병 정렬
배열이[9 106 7 8 34 5 1 2] 일케 있다면 이미 정렬이 되어있는 것끼리 합병한다는 의미입니다.
즉, 배열에서 이미 정렬된 [9 10] [5 6 7 8] [3 4 5] [1 2] 를 각각을 뭉탱이로 보고
두개씩 합병한다는 의미입니다. 그래서 위의 상태에서 한번 합병이 진행되면
[5 6 7 8 9 10] [1 2 3 4 5] 가 되고 한번 더 합병하면
[1 2 3 4 5 6 7 8 9 10]가 최종적으로 되어서 정렬이 된다는 의미입니다.

2. 토너먼트 정렬
스포츠에서 이긴사람이 토너먼트로 올라가는 것과 비슷한데요.. 먼저 완전이진트리를 만들고 단말노드들에 배열의 값을
전부넣습니다.그상태에서 대진표보면 16강에서 결승까지 올라가듯이 배열에서 복사한 단말노드 두개의 숫자를 비교해서
큰 수를 부모노드로복사하고 또 동일 레벨 노드들끼리 비교해서 위로 올리고를 반복합니다. 그러면 완전이진트리의
젤 위에는 배열의 원소중에서 젤 큰 숫자가 들어가게 됩니다. 그 큰 숫자는 배열중에서 젤 큰 숫자이고 방금까지의 과정을 한번
더 반복하면 그 다음으로 큰 숫자가 나오고 또 하면 또 그 다음으로 큰숫자가 나오고 이과정을 반복해서 정렬된
배열을 얻습니다.
=============================================================================
저의 문제점)
1. 자연합병정렬 : 제가 재귀함수를 구현하는게 굉장히 미흡합니다. 이거 진짜 며칠동안 해봤는데 어떻게 진행을 해야할지
모르겠습니다. 일단 이미 정렬된 런에서의 첫번째 값을 가진 배열인덱스를 기억해두었다가 하는 방법으로
해보기도 하고,런을 두개를 구한담에 합병먼저 해보려고도 해봤는데 왠지 뭔가 잘못된거같아서요..
구현을 어떤식으로 진행을 해야할까요?

2. 토너먼트 정렬 : 책에 설명은 먼저 완전이진트리를 만들고 단말노드에 배열의 값을 복사하는 게 첫단계고
두번째가 단말노드들의 값을 비교해서 부모노드에 복사하는건데요.
두번째 과정은 어떻게 해야할지 감을 잡았어요 근데 첫 번째 과정은 어떻게 해야할지 몰겠습니다.
첫번째 과정만 구현한다면 두번째는 할 수 있을 것 같습니다. 도와주세요 고수님들.. ㅜ.ㅡ

신청하기