[질문]merge sort~
글쓴이: 1anytime / 작성시간: 토, 2004/10/16 - 12:24오전
C 언를 시작한지 얼마 안되 초심자인데요....
===============================================
mergesort()함수를 2의 거듭제곱 크기에 대해서만이 아니라 임의의 크기의 배열에
대해서도 사용할 수 있도록 수정하시오. 이때 임의의 양수는 2의 거듭제곱의 합으로 표현할수 있음
===============================================
책내용중 일부인데요... 말을 이해할수가 없습니다. 어떤식으로 해야하는건지
설명좀 부탁드릴게요....
Forums:
정말 난해하군요...2^n 크기의 배열에서만 사용할 수 있는 me
정말 난해하군요...
2^n 크기의 배열에서만 사용할 수 있는 mergesort함수를
n개의 크기의 배열에서도 사용할 수 있게 고치라는 뜻인가요?
물론 n>0이겠고...
2^n인가요? n^2가요?
"이때 임의의 양수는 2의 거듭제곱의 합으로 표현할수 있음"는 힌트겠죠?
There is no spoon. Neo from the Matrix 1999.
그냥 짐작인데.. 머지 소트를 까먹은지도 꽤 돼었고..;아마 빈
그냥 짐작인데.. 머지 소트를 까먹은지도 꽤 돼었고..;
아마 빈 공간을 만들어서(전체 Data 수가 2^n개가 되게끔...) 거기에 NULL Data 대신에 2^n Data를 채워주는 게 아닌가 싶네요.
FFT도 그런식으로 하거든요.
도움이 되었으면 합니다.
"A Book on C"를 보시는군요.예를 들어 14개를 정렬하고 싶
"A Book on C"를 보시는군요.
예를 들어 14개를 정렬하고 싶다면 이런 식으로 하라는 뜻입니다.
14 = 8 + 4 + 2 (2의 거듭제곱의 합)
1. 8개를 merge sort하여 작업공간 0~7에 저장한다.
2. 이 위치(7)을 기억해둔다.
3. 다음 4개를 정렬하여 8~11에 저장한다.
4. 0~7과 8~11을 merge하고 위치 11을 기억해둔다.
5. 나머지 2개를 정렬하고 이전의 원소들과 merge한다.
별로 어렵지 않죠? :)