Sorting에 대한 짧은 정리(N(logN)^2, Shell정렬)
4. Shell Sortting Insertion Sorting은 N이 작을 경우와, 반정렬,정렬된상태(최선의 경우 O(N)) 소요 시간이 매우 짧다. 이를 이용한 Sorting으로 Divide and Conquor방법의 대표적인 예라고 할수 있다. 자료를 일정 부분(h)로 나누어서 각각에 대해서 insertion sorting을 하고 sorting된 전체 자료를 다시 h-1로 나누어서 각각에 대해서 insertion sorting하고 이 마지막으로 전체를 insertion sorting하는 방법이다. 예를 들어 8, 2, 9, 3, 4, 5, 7, 1 을 정렬한다면 h=3으로 하여 8,3,7 에 대해서 insertion sorting 2,4,1에 대해서 insertion sorting 9,5에 대해서 ..
2007. 4. 5.
Sorting에 대한 짧은 정리(나쁜 정렬)
정렬은 내부정렬과 외부 정렬이 있는데, 내부 정렬은 대상 자료를 모두 기억 장소에 읽어들여 정렬하는 것으로 Bubble,Selection,Insertion,Shell,Quick,Radix,Heap,Merge등이 있고 외부 정렬은 자료의 일부분만 기억장소에 읽어 들여 정렬하는 방법으로, 벨런스트, 캐스캐이드, 다상, 오실레이팅병합 정렬이 있다. 내부 정렬 1. Bubble Sorting 두개의 자료를 비교하여 자료를 맞바꾸는 방식으로 정렬 31, 15, 44, 13, 22가 있을 경우 31과 15를 비교하여 15,31,44,13,22로
2007. 4. 5.